GCDMAX - Ước chung lớn nhất lớn nhất
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.1s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho 2 số tự nhiên L,R. Tìm số nguyên m lớn nhất sao cho tồn tại 2 số nguyên ~ L\le a
Input
Gồm 2 số nguyên L ,R trên 1 dòng (~1\le L<R<10^7~).</p>
Output
In ra kết quả theo yêu cầu bài toán.
Sample
Input #1
3 6
Output #1
3
Hint
Trong ví dụ trên thì ta có các cặp số có thể có là: (3,4), (3,5), (3,6), (4,5), (4,6), (5,6) trong đó ~ \gcd{(3,6)}=3 ~ là lớn nhất vậy kết quả cần tìm là 3.
Bình luận
Thuật khác:
cnt = 0, cách check đó là duyệt các bội của ~i~ trong đoạn ~[i, r]~, nếu bội của ~i~ nằm trong đoạn ~[l, r]~ thì++cnt.cnt == 2thì tức là đã có ~1~ cặp số thoả mãn GCD của chúng là ~i~, suy ra ~i~ là đáp án bài toán.Hint: duyệt từ ~2e6~ về ~1~ cũng sẽ a xê nhé :D
Đề lỗi hiển thị lỗi quá: Đại loại là cho L và R tìm ước chung lớn nhất lớn nhất giữa 2 số bất kì trong đoạn [L, R]
Đề yêu cầu tìm gcd lớn nhất của 2 số bất kì trong đoạn [L, R] (tạm gọi số đó là g). Thì mình có 2 thứ cần quan tâm.
Thứ nhất chắc chắn phải có ít nhất 2 số trong đoạn [L, R] chia hết cho g, thứ hai g phải lớn nhất. Vậy lúc này bài toán đưa về tìm số x lớn nhất sao cho có ít nhất 2 số trong đoạn [L, R] chia hết cho nó. Mà để tìm số lượng số chia hết cho 1 số nằm trong đoạn [L, R] thì mình lấy R / x - (L - 1) / x để ra được số số chia hết cho x trong đoạn [L, R]. nhưng mà duyệt từ 1 -> R để check số lượng số chia hết cho từng con x một thì chắc chắn TLE. Giải pháp đó là chỉ tìm số x mà có <= 2 số chia hết cho nó trong đoạn [L, R].
R / x - (L - 1) / x <= 2
(R - L + 1) / x <= 2
(R - L + 1) / 2 <= x
Vậy ta cần check các số nằm trong đoạn từ (R - L + 1) / 2 đến R. Tuy nhiên vẫn sẽ TLE nên ta cần thêm 1 điều kiện giới hạn nữa. Ta sẽ chỉ duyệt từ [(R - L + 1) / 2, (R - L + 1)]. Lý do thì số x cần từ 2 số trở lên trong đoạn [L, R] chia hết cho nó mới đc coi là thoả mãn, vậy các số mà chỉ có 1 số trong đoạn [L, R] chia hết ta sẽ loại (ta check tăng dần nên x càng tăng thì số số chia hết của nó trong đoạn [L, R] càng giảm).
R / x - (L - 1) / x <= 1
(R - L + 1) / x <= 1
(R - L + 1) <= x (từ con x này trở đi này ta không cần check nữa vì kiểu gì nó cũng chỉ có <= 1 số trong đoạn [L, R] chia hết cho nó thôi)
Tóm lại là check các số trong đoạn [(R - L + 1) / 2, (R - L + 1)]. Số nào có số lượng số chia hết cho nó thuộc đoạn [L, R] mà >= 2 thì ta cập nhật thành kết quả. Tối ưu hơn nữa thì ta duyệt ngược lại, gặp số nào thoả mãn thì cập nhật vào kết quả rồi break. Lúc đầu nên để biến lưu kết quả = 1.
em lại nghĩ đọc thuật toán lại dễ hiểu hơn nghe anh giảng =))))))))
e cx nghĩ thế