Số thứ k (THT TQ 2015)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
letangphuquy
Dạng bài
Đ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


  • 16
    penistone    2:58 p.m. 19 Tháng 12, 2023 ← chỉnh sửa 19
    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


    • 0
      Haidepzai    10:13 p.m. 29 Tháng 7, 2024

      9 likes rồi kìa


      • 0
        penistone    2:30 p.m. 30 Tháng 7, 2024

        ok bạn, mình làm xong sol rồi kìa
        nó có thể hơi chi tiết qua, mong bạn thông cảm 😅

    1 bình luận nữa