Số thứ k (THT TQ 2015)
Xem PDF
Điểm:
900
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bài 1 năm 2015
Cho dãy \(A\) gồm các số nguyên dương tăng dần chia hết cho ít nhất một trong ba số \(3,5,7\).
Như vậy ta có dãy \(A = (3,5,6,7,9,10,12,14,15,18,20,...)\).
Yêu cầu đưa ra số thứ \(K\) trong dãy \(A\). Ví dụ, nếu \(K = 4\) thì đưa ra số \(7\).
Input
- Một dòng duy nhất chứa số \(K (1 \le K \le 10^{16})\)
Output
- Một dòng duy nhất chứa đáp án
Bình luận
Cách 1: duyệt
Đơn giản là duyệt các số từ 1 lên, kiểm tra xem số đó có chia hết cho 3, 5 hay 7 không. Nếu có chia hết thì cộng vào biến đếm. Khi biến đếm đạt đến giá trị \(K\) thì ta có thể in ra số thứ \(K\) mà chia hết cho 3,5 hay 7.
Cách làm này có độ phức tạp O(\(n\)). Tuy nhiên, vì giới hạn lên đến 10^16 nên đây là cách không hiệu quả để AC bài này.
Cách 2: tìm kiếm nhị phân
Chúng ta có thể biết được có bao nhiêu số chia hết cho \(k\) từ 1 -> \(n\) bằng cách lấy \(n\) chia \(k\), nên để đếm số lượng số chia hết cho 3 nhỏ hơn hoặc bằng \(n\), ta có thể lấy \(n\)/3. Tương tự với số 5 và 7.
Tuy nhiên, khi cộng \(n\)/3, \(n\)/5 và \(n\)/7 vào nhau, ta sẽ bị trùng các số chia hết cho cả 3 và 5, cả 5 và 7, và cả 3 và 7 nên ta phải trừ đi số lượng tương ứng (tức là trừ đi \(n\)/15 để loại bỏ các số bị trùng khi cùng chia hết cho 3 và 5 , tương tự với \(n\)/21 và \(n\)/35).
Nhưng khi trừ, chúng ta lại vô tình loại bỏ các số cùng chia hết cho 3, 5 và 7, nên để bù lại thì ta phải cộng lại \(n\)/105.
Tóm lại, chúng ta có công thức để tính số lượng số chia hết cho 3,5 hoặc 7 từ 1 -> \(n\) là: n/3+n/5+n/7-n/15-n/21-n/35+n/105 . Việc còn lại là chúng ta tìm kiếm nhị phân trong khoảng từ 1 -> 3\(n\) và kiểm tra xem số nào có số lượng số chia hết cho 3,5 hoặc 7 bằng \(K\) là xong.
Tuy nhiên, trong quá trình tìm kiếm nhị phân thì có các trường hợp, dù số tìm thấy đã có số lượng số chia hết cho 3,5 hoặc 7 bằng \(K\), nhưng bản thân số đó lại không chia hết cho 3,5 hoặc 7 (như số 8, có 4 số chia hết cho 3,5 hoặc 7 nhỏ hơn hoặc bằng 8, nhưng 8 lại không chia hết cho 3,5 hay 7). Vì vậy, chúng ta phải lùi lại giá trị tìm được sao cho nó chia hết cho 3,5 hoặc 7 thì thôi.
Bài giải:
C++: https://codebeautify.org/alleditor/y242b2c8a
Mình xin sol với ạ!