Hướng dẫn giải của [200 đề thầy Đức] Bài 86: Đọc sách
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Với mỗi truy vấn $(n, m)$, các trang chia hết cho $m$ là $m, 2m, \dots, tm$ với $t = \lfloor n/m \rfloor$. Cần tính tổng chữ số cuối của các số này. Có $q \le 1000$ truy vấn và $n, m$ đến $10^{16}$ nên không thể duyệt từng trang.
Sub 1: Vét cạn — ~O(n/m)~, dùng khi ~n, m \le 10^4~
Duyệt các trang $p = m, 2m, \dots$ không vượt quá $n$ và cộng $p \bmod 10$ vào tổng.
Kết quả chạy riêng sub này: đúng 10/21 test (11 test còn lại quá giờ, đều có $n$ hoặc $m$ lớn hơn miền của sub này).
Sub 2: Công thức theo chu kỳ 10 — ~O(1)~
Chữ số cuối của $jm$ chỉ phụ thuộc vào $j \bmod 10$, vì $(j+10)m \equiv jm \pmod{10}$. Gọi $S_{10}$ là tổng chữ số cuối của $jm$ với $j = 1, \dots, 10$. Với $t = \lfloor n/m \rfloor$:
$$\text{tổng} = \left\lfloor \frac{t}{10} \right\rfloor \cdot S_{10} + \sum_{j=1}^{t \bmod 10} (jm \bmod 10)$$
Bẫy cần chú ý: $t$ có thể lên tới $10^{16}$ và tổng có thể lên đến khoảng $9 \cdot 10^{16}$, nên dùng long long. Khi tính $jm$ với $j \le 10$ và $m \le 10^{16}$ thì tích khoảng $10^{17}$, vẫn nằm trong phạm vi long long.
Chương trình hoàn chỉnh
Chương trình đọc $q$ truy vấn. Với mỗi truy vấn, nếu $n, m \le 10^4$ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int q;
vector<long long> N, M; // các truy vấn (n, m)
// Các trang chia hết cho m là j*m với j = 1..t, t = n / m.
// Chữ số cuối của j*m chỉ phụ thuộc j mod 10, nên tổng theo chu kỳ 10.
// Sub 1: vét cạn — cộng trực tiếp chữ số cuối của từng trang chia hết cho m.
// Dùng khi mọi n, m <= 10^4
void sub1() {
for (int i = 0; i < q; i++) {
long long sum = 0;
for (long long p = M[i]; p <= N[i]; p += M[i])
sum += p % 10;
cout << sum << "\n";
}
}
// Sub 2: công thức theo chu kỳ 10.
// S10 = tổng chữ số cuối của j*m với j = 1..10. Với t = n/m:
// tổng = (t / 10) * S10 + tổng của j = 1..(t mod 10).
void sub2() {
for (int i = 0; i < q; i++) {
long long n = N[i], m = M[i];
long long t = n / m;
long long S10 = 0;
for (int j = 1; j <= 10; j++) S10 += ((long long)j * m) % 10;
long long sum = (t / 10) * S10;
for (long long j = 1; j <= t % 10; j++) sum += ((j * m) % 10); // phần lẻ của chu kỳ
cout << sum << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> q;
N.resize(q);
M.resize(q);
bool small = true;
for (int i = 0; i < q; i++) {
cin >> N[i] >> M[i];
if (N[i] > 10000 || M[i] > 10000) small = false;
}
if (small) sub1(); // mọi truy vấn nhỏ: vét cạn
else sub2(); // có truy vấn lớn: công thức
return 0;
}
Bình luận