Hướng dẫn giải của Bội đặc biệt (đề Đà Nẵng 2021)
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
Cho P (không chia hết cho 2 và 5) và N. Đếm số X chỉ gồm chữ số 9, có không quá N chữ số, và chia hết cho P.
Nhận xét: số gồm k chữ số 9 là X = 10^k - 1 (k >= 1). X chia hết cho P khi và chỉ khi 10^k ≡ 1 (mod P). Vì P nguyên tố cùng nhau với 10 nên tồn tại chu kỳ nhỏ nhất ord (số k nhỏ nhất >= 1 để 10^k ≡ 1) và các k thỏa mãn chính là các bội của ord. Vậy đáp án là N / ord (chia lấy phần nguyên).
Sub 1: Vét cạn — ~O(N)~, dùng khi ~N \le 10~
Với mỗi k từ 1 đến N, tạo trực tiếp số X gồm k chữ số 9 (X = X·10 + 9) rồi kiểm tra X chia hết cho P. Với N <= 10 số không vượt quá 10^10 nên dùng long long là đủ.
Chấm riêng sub này: đúng 9/20 test (các test có N <= 10 đều đúng).
Sub 2: Theo dõi phần dư — ~O(N)~, dùng khi ~N \le 160~
Thay vì tạo số lớn, chỉ giữ phần dư r = X mod P. Từ số gồm k chữ số 9 suy ra số gồm k+1 chữ số 9 bằng r = (r·10 + 9) mod P. Nếu r = 0 thì tính một số. Cách này không cần số lớn, nhưng vẫn phải duyệt đủ N bước.
Chấm riêng sub này: đúng 16/20 test (các test có N <= 160 đều đúng).
Sub 3: Chu kỳ của 10 modulo P — ~O(P)~, dùng cho N lớn
Tính 10^k mod P lần lượt cho đến khi bằng 1 (mod P), được chu kỳ ord. Khi đó đáp án là N / ord. Vì ord <= P nên vòng lặp chạy không quá P bước, đủ nhanh khi P <= 10^6.
Bẫy: với P = 1 thì mọi số đều chia hết, ord = 1 và đáp án là N. Khi so sánh với 1 nên viết 1 % P để trường hợp P = 1 cũng đúng.
Ví dụ: P = 7, N = 7. 10 mod 7 = 3, 3^2 = 2, 3^3 = 6, 3^4 = 4, 3^5 = 5, 3^6 = 1 nên ord = 6. Đáp án là 7 / 6 = 1, đúng với số X = 999999.
Chương trình hoàn chỉnh
main đọc P và N, nếu N <= 10 gọi sub1, nếu N <= 160 gọi sub2, còn lại gọi sub3.
#include <bits/stdc++.h>
using namespace std;
long long P, N;
// Nhận xét: số chỉ gồm k chữ số 9 là X = 10^k - 1, với k >= 1.
// X chia hết cho P <=> 10^k ≡ 1 (mod P). Vì P không chia hết cho 2 và 5 nên tồn tại chu kỳ nhỏ nhất
// ord (ord là cấp của 10 modulo P): các k thỏa mãn là bội của ord. Với 1 <= k <= N đáp án là N / ord.
// Sub 1: vét cạn — với mỗi k từ 1 đến N tạo trực tiếp số X = 10^k - 1 rồi kiểm tra chia hết cho P. Dùng khi N <= 10.
void sub1() {
long long cnt = 0, X = 0;
for (int k = 1; k <= N; k++) {
X = X * 10 + 9; // X gồm k chữ số 9 (N <= 10 nên không tràn long long)
if (X % P == 0) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: mô phỏng theo phần dư. r = X mod P với X gồm k chữ số 9, r = (r*10 + 9) mod P. O(N). Dùng khi N <= 160.
void sub2() {
long long cnt = 0, r = 0;
for (int k = 1; k <= N; k++) {
r = (r * 10 + 9) % P;
if (r == 0) cnt++;
}
cout << cnt << "\n";
}
// Sub 3: tìm chu kỳ ord = số k nhỏ nhất >= 1 sao cho 10^k ≡ 1 (mod P), rồi đáp án là N / ord. O(P). Dùng cho N lớn.
void sub3() {
long long pw = 10 % P; // 10^k mod P
long long ord = 1;
while (pw != 1 % P) {
pw = pw * 10 % P;
ord++;
}
cout << N / ord << "\n";
}
int main() {
freopen("boi.inp", "r", stdin);
freopen("boi.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> P >> N;
if (N <= 10) sub1(); // N nhỏ: tạo trực tiếp các số 9...9
else if (N <= 160) sub2(); // N vừa: theo dõi phần dư
else sub3(); // N lớn: chu kỳ của 10 modulo P
return 0;
}
Bình luận