Số May Mắn

Nguồn: Đề thi HSG Tin học (Câu 2 – 5 điểm) Độ khó: Khá Quy hoạch động QHĐ chữ số Đếm Vét cạn

Đề bài

Câu 2. Số may mắn (5 điểm)

Cho số nguyên dương $N$ và số nguyên dương $K$ $(0 \lt N \le 2 \times 10^9;\ 1 \le K \le 82)$. $M$ là tổng giá trị các chữ số của $N$. $N$ được gọi là số may mắn nếu $M$ chia hết cho $K$. Ví dụ: $N = 234$ và $K = 3$ thì $N$ là số may mắn vì $N$ có tổng các chữ số là $M = 2 + 3 + 4 = 9$ chia hết cho 3.

Cho 2 số nguyên dương $P$ và $Q$ $(0 \lt P \le Q \le 2 \times 10^9)$.

Yêu cầu: Hãy đếm số lượng các số may mắn nằm trong đoạn $[P, Q]$.

Dữ liệu vào: Vào từ file Bai2.inp gồm 1 dòng chứa 3 số $P$, $Q$, $K$, mỗi số cách nhau 1 dấu cách.

Dữ liệu ra: Ghi ra file Bai2.out gồm 1 dòng chứa số $D$ là số lượng các số may mắn tìm được.

(Code trong bài đọc/ghi chuẩn – bàn phím/màn hình. Nếu chấm bằng file thì các bạn thêm freopen("Bai2.inp", "r", stdin); freopen("Bai2.out", "w", stdout); vào đầu hàm main nhé.)

Ví dụ 1 – Bai2.inp

1 30 3

Ví dụ 1 – Bai2.out

10

Ví dụ 2 – Bai2.inp

10 30 10

Ví dụ 2 – Bai2.out

2

Lời mở đầu

Bữa giờ LeetCode hoài sợ anh em ngán 😅 Nay mình đi comment dạo thấy bài này cũng được nên đăng để anh em thử sức nhé. Bạn hỏi bài than là "số to quá em không làm được" – đúng rồi, $Q$ lên tới $2 \cdot 10^9$ nên duyệt từng số là không ổn. Đây là một bài rất hay để làm quen với quy hoạch động chữ số (digit DP), một kỹ thuật hay gặp trong các đề thi HSG. Chúc anh em học tốt và gặt hái nhiều thành công 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ cho bạn nào chưa hiểu đề:

• Ví dụ 1 ($P = 1, Q = 30, K = 3$): một số chia hết cho 3 khi và chỉ khi tổng chữ số chia hết cho 3, nên các số may mắn chính là $3, 6, 9, 12, 15, 18, 21, 24, 27, 30$ ⇒ 10 số.
• Ví dụ 2 ($P = 10, Q = 30, K = 10$): cần tổng chữ số là 10 hoặc 20. Trong đoạn $[10, 30]$ chỉ có $19$ ($1 + 9 = 10$) và $28$ ($2 + 8 = 10$) ⇒ 2 số.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Duyệt từng số · O((Q − P) · 10)Cách 2QHĐ chữ số · gần như O(1)

Cách 1Duyệt từng số trong đoạn – O((Q − P) · 10)

Làm đúng theo đề: duyệt $x$ từ $P$ đến $Q$, tính tổng chữ số của $x$ (lấy x % 10 rồi x /= 10 cho tới khi hết), nếu tổng chia hết cho $K$ thì đếm. Cách này viết 5 phút là xong và chắc chắn đúng, rất nên dùng để kiểm tra cách nhanh ở dưới.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int tongChuSo(long long x){
    int s = 0;
    while(x > 0){
        s += x % 10;
        x /= 10;
    }
    return s;
}

int main(){
    long long P, Q, K;
    cin >> P >> Q >> K;
    long long cnt = 0;
    for(long long x = P; x <= Q; x++){
        if(tongChuSo(x) % K == 0){
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

def tong_chu_so(x):
    s = 0
    while x > 0:
        s += x % 10
        x //= 10
    return s


P, Q, K = map(int, input().split())
cnt = 0
for x in range(P, Q + 1):
    if tong_chu_so(x) % K == 0:
        cnt += 1
print(cnt)

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ vài biến ⇒ $O(1)$.
• Thời gian: $Q - P + 1$ số, mỗi số tách tối đa 10 chữ số ⇒ $O((Q - P) \cdot 10)$.

Không gian$O(1)$

Thời gian$O((Q - P) \cdot \log_{10} Q)$

Số to quá thì TLE

Với $P = 1$, $Q = 2 \cdot 10^9$ mình đo thử bản C++ mất khoảng 27 giây (Python còn lâu hơn nhiều) ⇒ chỉ ăn được các test có đoạn $[P, Q]$ ngắn (cỡ $10^7$ trở xuống).

Cách 2Quy hoạch động chữ số

Bước 1: đưa về đếm trên đoạn [0, X]

Gọi $dem(X)$ = số lượng số $x$ trong đoạn $[0, X]$ có tổng chữ số chia hết cho $K$. Khi đó, giống như mảng cộng dồn:

Đếm trên đoạn = hiệu hai "tiền tố"

$D = dem(Q) - dem(P - 1)$
(Số $0$ có tổng chữ số bằng 0, chia hết cho $K$, nên được đếm trong cả hai $dem$ và tự triệt tiêu – không ảnh hưởng đáp án.)

Bước 2: một số x < X trông như thế nào?

Viết $X$ thành xâu $n$ chữ số $c_0 c_1 \ldots c_{n-1}$, và viết mọi số $x \le X$ cũng đủ $n$ chữ số bằng cách thêm số 0 ở đầu (thêm số 0 không làm đổi tổng chữ số). Nếu $x \lt X$ thì so sánh từ trái sang phải, sẽ có một vị trí $i$ đầu tiên mà hai số khác nhau, và ở đó chữ số của $x$ nhỏ hơn:

Số Xc₀c₁…cᵢ…cₙ₋₁

Số xc₀c₁…d**

xanh: giống hệt $X$ (tổng là $pre$) · vàng: chữ số $d \lt c_i$ · sọc tím: $rem = n - 1 - i$ chữ số tự do, chọn gì cũng được (0..9) mà vẫn $\lt X$.

Vậy với mỗi vị trí $i$ và mỗi chữ số $d \lt c_i$, ta cần đếm: có bao nhiêu cách điền $rem$ chữ số tự do sao cho $pre + d + (\text{tổng phần tự do})$ chia hết cho $K$. Nếu biết

Bảng QHĐ

$f[len][s]$ = số dãy gồm $len$ chữ số (mỗi chữ số từ 0 đến 9) có tổng đúng bằng $s$
thì đáp án cho cặp $(i, d)$ là $\displaystyle\sum_{t \,:\, (pre + d + t) \bmod K = 0} f[rem][t]$, với $t$ chạy từ $0$ đến $9 \cdot rem$.

Cuối cùng còn chính số $X$ (trường hợp không có vị trí nào nhỏ hơn): nếu tổng chữ số của $X$ chia hết cho $K$ thì cộng thêm 1.

Bước 3: tính bảng f

Dãy $len$ chữ số có tổng $s$ = chọn chữ số cuối là $d$ (0..9), phần còn lại là dãy $len - 1$ chữ số có tổng $s - d$:

Công thức truy hồi

$f[0][0] = 1,\quad f[len][s] = \displaystyle\sum_{d = 0}^{\min(9, s)} f[len - 1][s - d]$

Vài dòng đầu của bảng (cột là $s$):

len \ s	0	1	2	3	4	5	6	7	8	9	10	11	12	…	18
0	1	0	0	0	0	0	0	0	0	0	0	0	0	…	0
1	1	1	1	1	1	1	1	1	1	1	0	0	0	…	0
2	1	2	3	4	5	6	7	8	9	10	9	8	7	…	1

Ví dụ $f[2][10] = 9$: các cặp chữ số có tổng 10 là $19, 28, 37, 46, 55, 64, 73, 82, 91$. Số lớn nhất trong đề là $2 \cdot 10^9$ (10 chữ số) nên chỉ cần $len \le 9$ và $s \le 81$ – bảng rất nhỏ.

Vì sao K ≤ 82?

Số $\le 2 \cdot 10^9$ có tổng chữ số lớn nhất là $1 + 9 \cdot 9 = 82$ (số $1\,999\,999\,999$). Nên với $K = 82$ chỉ có đúng 1 số may mắn trong $[1, 2 \cdot 10^9]$. Đề cho $K \le 82$ cũng vì vậy. Code của mình không phụ thuộc giới hạn này, chỉ duyệt $t$ và kiểm tra chia hết thôi.

Minh hoạ cách đếm dem(X)

Em nhập $X$ và $K$ rồi bấm Tiếp. Mỗi bước là một "khuôn" số: phần xanh giữ giống $X$, ô vàng là chữ số $d$ nhỏ hơn, các ô sọc tím là chữ số tự do. Khung cho biết khuôn đó đóng góp bao nhiêu số may mắn.

X K

Ví dụ nhanh:

Ví dụ $dem(30)$ với $K = 3$: khuôn 0* có $f[1][0] + f[1][3] + f[1][6] + f[1][9] = 4$ số ($0, 3, 6, 9$), khuôn 1* có 3 số ($12, 15, 18$), khuôn 2* có 3 số ($21, 24, 27$), cộng chính số $30$ ⇒ $dem(30) = 11$. Còn $dem(0) = 1$ (số 0) ⇒ đáp án $11 - 1 = 10$, đúng ví dụ 1.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

long long f[11][91]; // f[len][s] = số dãy len chữ số (0..9) có tổng bằng s
long long K;

long long dem(long long X){ // đếm số x trong [0, X] có tổng chữ số chia hết cho K
    if(X < 0) return 0;
    string s = to_string(X);
    int n = s.size();
    long long res = 0;
    int pre = 0; // tổng các chữ số đã giữ giống X
    for(int i = 0; i < n; i++){
        int c = s[i] - '0';
        int rem = n - 1 - i;
        for(int d = 0; d < c; d++){
            for(int t = 0; t <= 9 * rem; t++){
                if((pre + d + t) % K == 0) res += f[rem][t];
            }
        }
        pre += c;
    }
    if(pre % K == 0) res++; // chính số X
    return res;
}

int main(){
    long long P, Q;
    cin >> P >> Q >> K;
    int n = to_string(Q).size();
    f[0][0] = 1;
    for(int len = 1; len < n; len++){
        for(int s = 0; s <= 9 * len; s++){
            for(int d = 0; d <= 9 && d <= s; d++){
                f[len][s] += f[len - 1][s - d];
            }
        }
    }
    cout << dem(Q) - dem(P - 1);
    return 0;
}

P, Q, K = map(int, input().split())
n = len(str(Q))
# f[length][s] = số dãy length chữ số (0..9) có tổng bằng s
f = [[0] * 91 for _ in range(11)]
f[0][0] = 1
for length in range(1, n):
    for s in range(9 * length + 1):
        for d in range(min(9, s) + 1):
            f[length][s] += f[length - 1][s - d]


def dem(X):
    # đếm số x trong [0, X] có tổng chữ số chia hết cho K
    if X < 0:
        return 0
    s = str(X)
    n = len(s)
    res = 0
    pre = 0  # tổng các chữ số đã giữ giống X
    for i in range(n):
        c = int(s[i])
        rem = n - 1 - i
        for d in range(c):
            for t in range(9 * rem + 1):
                if (pre + d + t) % K == 0:
                    res += f[rem][t]
        pre += c
    if pre % K == 0:  # chính số X
        res += 1
    return res


print(dem(Q) - dem(P - 1))

C++▶ Chạy tay từng dòng codeCách 2: tính bảng f[len][s], rồi D = dem(Q) − dem(P − 1). Vòng t được gom thành 1 bước cho mỗi d.

Dữ liệu vào (stdin) – sửa thoải mái1 30 3

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4long long f[11][91]; // f[len][s] = số dãy len chữ số (0..9) có tổng bằng s

5long long K;

6

7long long dem(long long X){ // đếm số x trong [0, X] có tổng chữ số chia hết cho K

8 if(X < 0) return 0;

9 string s = to_string(X);

10 int n = s.size();

11 long long res = 0;

12 int pre = 0; // tổng các chữ số đã giữ giống X

13 for(int i = 0; i < n; i++){

14 int c = s[i] - '0';

15 int rem = n - 1 - i;

16 for(int d = 0; d < c; d++){

17 for(int t = 0; t <= 9 * rem; t++){

18 if((pre + d + t) % K == 0) res += f[rem][t];

19 }

20 }

21 pre += c;

22 }

23 if(pre % K == 0) res++; // chính số X

24 return res;

25}

26

27int main(){

28 long long P, Q;

29 cin >> P >> Q >> K;

30 int n = to_string(Q).size();

31 f[0][0] = 1;

32 for(int len = 1; len < n; len++){

33 for(int s = 0; s <= 9 * len; s++){

34 for(int d = 0; d <= 9 && d <= s; d++){

35 f[len][s] += f[len - 1][s - d];

36 }

37 }

38 }

39 cout << dem(Q) - dem(P - 1);

40 return 0;

41}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: bảng $f$ cỡ $11 \times 91$ (số chữ số × tổng chữ số lớn nhất) ⇒ $O(\log^2 Q)$, coi như hằng số.
• Thời gian: tính bảng $f$ mất khoảng $10 \cdot 90 \cdot 10$ phép cộng; mỗi lần gọi $dem$ duyệt tối đa $10$ vị trí × $9$ chữ số $d$ × $82$ giá trị $t$ ≈ $7\,400$ phép tính. Tổng cộng chỉ vài chục nghìn phép tính dù $Q = 2 \cdot 10^9$ – chạy tức thì nha các bạn.

Không gian$O(\log^2 Q)$

Thời gian$O(10 \cdot \log^2 Q)$

Mấy chỗ dễ sai

• Đừng quên chính số X (dòng if(pre % K == 0) res++), thiếu dòng này là đếm thiếu khi $Q$ là số may mắn.
• Giá trị của $f$ và kết quả có thể lên tới cỡ $2 \cdot 10^9$, vượt int ⇒ dùng long long.
• Gọi dem(P - 1) chứ không phải dem(P), nếu không sẽ mất số $P$.

Ghi chú của mình: code C++ và Python của cách 2 đã được kiểm tra với 400 bộ test ngẫu nhiên ($Q \le 10^5$, $K$ từ 1 đến 82, có cả $P = 1$, $P = Q$ và $Q$ dạng $10^k$), so với code vét cạn của cách 1 – khớp hết. Ngoài ra mình so thêm đoạn $[1\,999\,000\,000;\ 2 \cdot 10^9]$ với $K = 7$ (vét cạn và QHĐ đều ra 142880), và kiểm tra vài kết quả biết trước: $P = 1, Q = 2 \cdot 10^9$ với $K = 1$ ra $2 \cdot 10^9$, với $K = 3$ ra $666\,666\,666$, với $K = 82$ ra 1. Với $Q = 2 \cdot 10^9$ cách 2 chạy tức thì (Python khoảng 0.02 giây), còn cách 1 bản C++ mất khoảng 27 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇