Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Đếm số có tổng chữ số chia hết K (Digit DP)

    Đếm số lượng số nguyên xxx trong đoạn [L,R][L, R][L,R] sao cho tổng các chữ số của xxx chia hết cho KKK.

    Ví dụ với L=1,R=20,K=3L=1, R=20, K=3L=1,R=20,K=3: các số thỏa mãn là 3,6,9,12,15,183,6,9,12,15,183,6,9,12,15,18 và cả 303030? không — chỉ trong [1,20][1,20][1,20], kết quả 666.

    • Định dạng đầu vào:

      Một dòng: ba số LLL, RRR, KKK.

    • Ràng buộc đầu vào:

      0≤L≤R≤10180 \le L \le R \le 10^{18}0≤L≤R≤1018, 1≤K≤1001 \le K \le 1001≤K≤100.

    • Định dạng đầu ra:

      Một số nguyên: số lượng số thỏa mãn.

    Ví dụ:

    Đầu vào:

    1 20 3

    Đầu ra:

    6

    Giải thích:

    Các số có tổng chữ số chia hết 3 trong [1,20]: 3,6,9,12,15,18 — đúng 6 số.

    Đang tải editor...