Tổng Các Chữ Số
Đề bài
Đan rất yêu thích số học và thường tự thử thách bản thân bằng những bài toán tự nghĩ ra. Một bài toán mà Đan nghĩ ra như sau: cho số nguyên dương $n$ và $k$, cần tính tổng các chữ số của các số tự nhiên không vượt quá $n$ và chia hết cho $k$.
Input: gồm hai dòng, mỗi dòng chứa hai số nguyên dương $n, k$ ($k \le n$) tương ứng với bộ cần tính.
Output: in ra hai dòng, mỗi dòng chứa một số nguyên là tổng các chữ số của các số tự nhiên không vượt quá $n$ và chia hết cho $k$, tương ứng với bộ trong dữ liệu vào.
Scoring
- Subtask 1 (30% số điểm): $n \le 10^6$.
- Subtask 2 (30% số điểm): $n = 10^x$ với $1 \le x \le 12$.
- Subtask 3 (40% số điểm): $n \le 10^{12}$.
5 2
25 106
3Giải thích ví dụ:
| n k | Các số ≤ n chia hết cho k | Tổng chữ số | Kết quả |
|---|---|---|---|
| 5 2 | 2, 4 | 2 + 4 | 6 |
| 25 10 | 10, 20 | (1 + 0) + (2 + 0) | 3 |
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
30%Subtask 1: duyệt hết – O(n)
Duyệt hết từ 1 đến $n$, nếu số đó chia hết cho $k$ thì tính tổng các chữ số của nó. Mà thay vì duyệt từng số rồi kiểm tra chia hết, ta nhảy thẳng theo bước $k$: $k, 2k, 3k, \ldots$ là được ngay các số chia hết cho $k$. Với mỗi số, tách từng chữ số bằng cách lấy % 10 rồi / 10 cho đến khi về 0.
Độ phức tạp: xấp xỉ $O(n)$ (chính xác hơn là $O(\frac{n}{k} \cdot \log_{10} n)$).
while(cin >> n >> k) (Python thì for line in sys.stdin) để đọc tới hết dữ liệu, có bao nhiêu bộ thì xử lý bấy nhiêu bộ.Xem code subtask 1
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
while(cin >> n >> k){
long long ans=0;
for (long long i=k;i<=n;i+=k){
long long h=i;
while (h!=0){
ans+=h%10;
h/=10;
}
}
cout<<ans<<endl;
}
return 0;
}import sys
for line in sys.stdin:
if not line.strip():
continue
n, k = map(int, line.split())
ans = 0
for i in range(k, n + 1, k):
h = i
while h != 0:
ans += h % 10
h //= 10
print(ans)+30%Subtask 2: n là lũy thừa của 10
Ta có hai trường hợp sau:
- Nếu $k$ lớn (ví dụ $k \ge 10^6$), số lượng số chia hết cho $k$ sẽ nhỏ hơn hoặc bằng $n / k \le 10^6$, lúc này ta chỉ cần duyệt trâu như subtask 1.
- Trường hợp còn lại, ta thấy rằng $n$ là lũy thừa của 10. Gọi số chữ số của $n$ là $x$, ta nhận xét rằng những số có số chữ số nhỏ hơn $x$ đều được xét đến, và ta chỉ cần xét riêng trường hợp $n$ có chia hết cho $k$ hay không ($n$ là số duy nhất có $x$ chữ số). Giả sử một số có ít hơn $x - 1$ chữ số, ta sẽ coi chúng có những chữ số 0 đằng trước (sao cho đủ $x - 1$ chữ số để thuận tiện xử lý). Ví dụ $n = 1000$ thì số 7 được coi là
007, số 42 được coi là042; thêm số 0 đằng trước không làm thay đổi tổng chữ số cũng như số dư.
Ta gọi:
- $f_{i,j}$ là tổng các chữ số của các số mà mới xét đến $i$ chữ số đầu, và phần đã xét đồng dư $j$ theo mod $k$;
- $num_{i,j}$ là số lượng số thỏa các điều kiện trên.
Ta có công thức sau, với $dg$ ($0 \le dg \le 9$) là chữ số thứ $i + 1$ tiếp theo được điền vào:
num[i+1][(j·10 + dg) mod k] += num[i][j]
Vì ta sẽ thêm $dg$ vào đằng sau $num_{i,j}$ số nên tổng các chữ số được cộng thêm vào là $num_{i,j} \cdot dg$. Còn số dư mới thì đơn giản: viết thêm 1 chữ số vào cuối nghĩa là nhân 10 rồi cộng chữ số đó, nên số dư mới là $(j \cdot 10 + dg) \bmod k$.
Khởi tạo $num_{0,0} = 1$ (chưa điền chữ số nào, có đúng 1 "số rỗng" với số dư 0). Đáp án là $f_{x-1,0}$ cộng thêm tổng chữ số của chính $n$ nếu $n$ chia hết cho $k$ (mà $n = 10^{x-1}$ có tổng chữ số đúng bằng 1, nên chỉ việc cộng thêm (n % k == 0)).
| j = 0 | j = 1 | j = 2 | |
|---|---|---|---|
| i = 0 | num = 1 f = 0 | num = 0 f = 0 | num = 0 f = 0 |
| i = 1 | num = 4 f = 18 | num = 3 f = 12 | num = 3 f = 15 |
| i = 2 | num = 34 f = 306 | num = 33 f = 294 | num = 33 f = 300 |
Ví dụ $n = 100$, $k = 3$: $n$ có $x = 3$ chữ số nên ta chỉ cần xét các số có 2 chữ số (từ 00 đến 99). Ô $f_{2,0} = 306$ chính là tổng các chữ số của mọi số từ 00 đến 99 chia hết cho 3; cộng thêm phần của chính $n = 100$ (100 không chia hết cho 3 nên cộng 0), đáp án là 306, khớp với cách duyệt trâu.
Số trạng thái là $13 \times k$, mỗi trạng thái thử 10 chữ số, nên độ phức tạp là $O(13 \cdot 10 \cdot k)$. Vì vậy trong code mình chỉ dùng DP khi $k \le 5 \cdot 10^5$ (đúng bằng kích thước mảng); còn $k$ lớn hơn thì số lượng bội của $k$ không vượt quá $n / k \le 2 \cdot 10^6$, quay về duyệt trâu như subtask 1 là đủ nhanh.
Xem code subtask 2
#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long f[15][500001]={};
long long num[15][500001]={};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
while (cin>>n>>k){
if ((n == 10 || n == 100 || n == 1000 || n == 10000
|| n == 100000 || n == 1000000 || n == 10000000
|| n == 100000000 || n == 1000000000 || n == 10000000000
|| n == 100000000000 || n == 1000000000000) && k <= 500000){
memset(f,0,sizeof(f));
memset(num,0,sizeof(num));
long long g=n;
vector<int> digit;
while (g!=0){
digit.push_back(g%10);
g/=10;
}
reverse(digit.begin(),digit.end());
f[0][0]=0;
num[0][0]=1;
for (int i=0;i<digit.size() - 1;i++){
for (int u=0;u<k;u++){
if (!num[i][u]) continue;
for (int ch=0;ch<=9;ch++){
f[i+1][(u*10+ch)%k]+=f[i][u]+ch*num[i][u];
num[i+1][(u*10+ch)%k]+=num[i][u];
}
}
}
cout<<f[digit.size() - 1][0] + (n % k == 0)<<endl;
}
else{
long long ans=0;
for (long long i=k;i<=n;i+=k){
long long h=i;
while (h!=0){
ans+=h%10;
h/=10;
}
}
cout<<ans<<endl;
}
}
}import sys
for line in sys.stdin:
if not line.strip():
continue
n, k = map(int, line.split())
special = {
10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000,
10000000000, 100000000000, 1000000000000
}
if n in special and k <= 500000:
f = [[0] * (k + 1) for _ in range(15)]
num = [[0] * (k + 1) for _ in range(15)]
g = n
digit = []
while g != 0:
digit.append(g % 10)
g //= 10
digit.reverse()
f[0][0] = 0
num[0][0] = 1
for i in range(len(digit) - 1):
for u in range(k):
if num[i][u] == 0:
continue
for ch in range(10):
f[i + 1][(u * 10 + ch) % k] += f[i][u] + ch * num[i][u]
num[i + 1][(u * 10 + ch) % k] += num[i][u]
print(f[len(digit) - 1][0] + (1 if n % k == 0 else 0))
else:
ans = 0
for i in range(k, n + 1, k):
h = i
while h != 0:
ans += h % 10
h //= 10
print(ans)(u*10+ch)%k sẽ vượt ra ngoài mảng f[15][500001]. Vì vậy mình thêm điều kiện k <= 500000 vào nhánh DP, đúng như ý tưởng "k lớn thì duyệt trâu" ở trên.100%Subtask 3: n bất kỳ ≤ 10¹² – thêm trạng thái "tiền tố của n"
Giữ nguyên tư tưởng của subtask 2, ta sẽ thêm một trạng thái nữa: $f_{i,j,g}$ là tổng các chữ số khi xét đến $i$ chữ số đầu và đồng dư $j$ mod $k$; $g = 1$ nếu $i$ chữ số đang xét vẫn là tiền tố của $n$ (tức là đang đi "sát" theo $n$), $g = 0$ thì ngược lại. Lúc này ta coi mọi số đều có đủ $x$ chữ số (thêm số 0 đằng trước), đúng bằng số chữ số của $n$.
Xét các $dg$ ($0 \le dg \le 9$) sẽ là chữ số thứ $i + 1$ tiếp theo:
- Nếu $g = 0$, thì có nghĩa là trước đó đã có một chữ số khiến số hiện tại nhỏ hơn $n$, nên điền chữ số nào cũng được, do đó:
f[i+1][(j·10+dg) mod k][0] += f[i][j][0] + dg · num[i][j][0]
num[i+1][(j·10+dg) mod k][0] += num[i][j][0] - Nếu $g = 1$, có nghĩa là số hiện tại vẫn còn là tiền tố của $n$:
- Nếu $dg$ lớn hơn chữ số thứ $i + 1$ của $n$, nghĩa là không thể điền $dg$ vô tiếp được vì sẽ làm số hiện tại đang xét lớn hơn hẳn $n$.
- Nếu $dg$ bằng với chữ số thứ $i + 1$ của $n$, số được tạo ra tiếp theo vẫn là tiền tố của $n$, do đó:
f[i+1][(j·10+dg) mod k][1] += f[i][j][1] + dg · num[i][j][1]
num[i+1][(j·10+dg) mod k][1] += num[i][j][1] - Nếu $dg$ nhỏ hơn chữ số thứ $i + 1$ của $n$, số được tạo tiếp theo sẽ nhỏ hơn hẳn $n$, do đó:
f[i+1][(j·10+dg) mod k][0] += f[i][j][1] + dg · num[i][j][1]
num[i+1][(j·10+dg) mod k][0] += num[i][j][1]
Khởi tạo $num_{0,0,1} = 1$ (chưa điền gì thì vẫn đang "sát" theo $n$). Đáp án là $f_{x,0,0} + f_{x,0,1}$: tổng chữ số của mọi số $\le n$ (kể cả chính $n$, ứng với $g = 1$) có số dư 0, tức là chia hết cho $k$. Số 0 cũng được đếm nhưng tổng chữ số của nó bằng 0 nên không ảnh hưởng gì. Trong code, chỗ int lim=j?digit[i]:9; chính là giới hạn chữ số được điền: đang sát theo $n$ thì không được vượt chữ số tương ứng của $n$, còn không thì điền thoải mái từ 0 đến 9. Và trường hợp $k \gt 5 \cdot 10^5$ vẫn quay về duyệt trâu như subtask 2.
Em nhập $n$, $k$ (nhỏ thôi) rồi bấm Tiếp để xem DP chữ số "gom" các tiền tố như thế nào: sau mỗi lần điền thêm 1 chữ số, các tiền tố có cùng số dư và cùng trạng thái "sát n" được gom vào một ô, ta chỉ cần nhớ num (bao nhiêu tiền tố) và f (tổng chữ số của chúng):
#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long f[15][2][500001]={};
long long num[15][2][500001]={};
long long maxN=500000;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
while (cin>>n>>k){
memset(f,0,sizeof(f));
memset(num,0,sizeof(num));
if (k<=maxN){
long long g=n;
vector<int> digit;
while (g!=0){
digit.push_back(g%10);
g/=10;
}
reverse(digit.begin(),digit.end());
// j = 0 k tien to, j = 1 tien to
f[0][1][0]=0;
num[0][1][0]=1;
for (int i=0;i<digit.size();i++){
for (int j=0;j<=1;j++){
for (int u=0;u<k;u++){
if (!num[i][j][u]) continue;
int lim=j?digit[i]:9;
for (int ch=0;ch<=lim;ch++){
f[i+1][(ch==digit[i]&&j)?1:0][(u*10+ch)%k]
+= f[i][j][u]+ch*num[i][j][u];
num[i+1][(ch==digit[i]&&j)?1:0][(u*10+ch)%k]
+=num[i][j][u];
}
}
}
}
cout<<f[digit.size()][1][0]+f[digit.size()][0][0]<<endl;
}
else{
long long ans=0;
for (long long i=k;i<=n;i+=k){
long long h=i;
while (h!=0){
ans+=h%10;
h/=10;
}
}
cout<<ans<<endl;
}
}
}import sys
maxN = 500000
for line in sys.stdin:
if not line.strip():
continue
n, k = map(int, line.split())
if k <= maxN:
f = [[[0] * k for _ in range(2)] for _ in range(15)]
num = [[[0] * k for _ in range(2)] for _ in range(15)]
g = n
digit = []
while g != 0:
digit.append(g % 10)
g //= 10
digit.reverse()
f[0][1][0] = 0
num[0][1][0] = 1
for i in range(len(digit)):
for j in (0, 1):
for u in range(k):
if num[i][j][u] == 0:
continue
lim = digit[i] if j == 1 else 9
for ch in range(lim + 1):
nj = 1 if (j == 1 and ch == digit[i]) else 0
nu = (u * 10 + ch) % k
f[i + 1][nj][nu] += f[i][j][u] + ch * num[i][j][u]
num[i + 1][nj][nu] += num[i][j][u]
print(f[len(digit)][1][0] + f[len(digit)][0][0])
else:
ans = 0
for i in range(k, n + 1, k):
h = i
while h != 0:
ans += h % 10
h //= 10
print(ans)Mình đã kiểm tra cả 3 bản code với hàng trăm bộ test ngẫu nhiên, so với cách duyệt trâu đều ra cùng kết quả. Bản C++ với $n = 10^{12}$, $k = 499999$ chạy khoảng 0.3 giây. Lưu ý 2 mảng long long [15][2][500001] tốn khoảng 240 MB bộ nhớ; nếu hệ thống chấm giới hạn bộ nhớ thấp hơn thì có thể chỉ giữ 2 tầng i và i + 1 (mảng lăn) là đủ. Bản Python cùng ý tưởng mất khoảng 20 giây khi $k$ gần $5 \cdot 10^5$ vì phải duyệt hàng chục triệu trạng thái, nên với subtask lớn các bạn nên nộp bản C++ nhé.
Nhận xét
Đăng nhận xét