Hướng dẫn giải của [Beginner Free Contest 13] BIGMOD
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
Tính ~A^B \bmod MOD~ với ~A, B~ có tới 100000 chữ số (đọc dưới dạng xâu) và ~MOD \le 10^9 + 10~. Không thể nhân lặp ~B~ lần, cần rút gọn số mũ.
Sub 1: ~MOD = 10~ — ~O(|A| + |B|)~
Chữ số cuối của ~A^B~ chỉ phụ thuộc chữ số cuối của ~A~ và lặp với chu kỳ 4 theo số mũ (kể từ số mũ 1). Ta lấy ~e = B \bmod 4~ (nếu bằng 0 thì đặt 4) rồi tính ~(A \bmod 10)^e \bmod 10~. Nếu chỉ nộp sub này: đúng 2/10 test.
Sub 2: ~MOD~ bất kỳ — định lý Euler mở rộng
Tính ~\varphi(MOD)~ bằng phân tích thừa số (thử chia đến ~\sqrt{MOD}~). Nếu ~MOD~ là số nguyên tố thì ~\varphi = MOD - 1~ (định lý Fermat). Tổng quát, với ~B \ge 40~ (lớn hơn số mũ lớn nhất của một ước nguyên tố trong ~MOD~, vì ~MOD < 2^{30}~) ta có ~A^B \equiv A^{(B \bmod \varphi) + \varphi} \pmod{MOD}~ kể cả khi ~A~ và ~MOD~ không nguyên tố cùng nhau (nên không được chỉ dùng ~B \bmod \varphi~). Với ~B < 40~ tính trực tiếp. Các số lớn được rút gọn bằng cách đọc xâu từng chữ số: ~r = (10 r + d) \bmod m~. Phép nhân modulo cần long long vì ~MOD~ đến ~10^9~. Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Hàm main đọc ~A, B, MOD~ dưới dạng xâu, nếu ~MOD = 10~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Kết quả: 10/10 test.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string A, B;
ll MOD;
ll strmod(const string& s, ll m) {
ll r = 0;
for (char c : s) r = (r * 10 + (c - '0')) % m;
return r;
}
ll power(ll a, ll e, ll m) {
ll r = 1 % m;
a %= m;
while (e) {
if (e & 1) r = r * a % m;
a = a * a % m;
e >>= 1;
}
return r;
}
// Sub 1: MOD = 10 — chữ số cuối của lũy thừa lặp với chu kỳ 4 (kể từ số mũ 1)
void sub1() {
ll a = A.back() - '0';
ll e = strmod(B, 4);
if (e == 0) e = 4;
cout << power(a, e, 10) << "\n";
}
// Sub 2: MOD bất kỳ — định lý Euler mở rộng:
// nếu B >= 40 (lớn hơn mọi số mũ nguyên tố trong MOD) thì A^B = A^(B mod phi + phi) (mod MOD)
void sub2() {
ll phi = MOD, t = MOD;
for (ll p = 2; p * p <= t; p++)
if (t % p == 0) {
while (t % p == 0) t /= p;
phi = phi / p * (p - 1);
}
if (t > 1) phi = phi / t * (t - 1);
ll a = strmod(A, MOD);
ll e;
bool small = B.size() <= 2 && stoll(B) < 40;
if (small) e = stoll(B);
else e = strmod(B, phi) + phi;
cout << power(a, e, MOD) << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> A >> B >> MOD;
if (MOD == 10) sub1();
else sub2();
return 0;
}
Bình luận