Hướng dẫn giải của Bài 3 (đề An Giang 2021)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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ìm a nhỏ nhất với N chia hết a^a.
Sub 1: Vét cạn, ~O(N \log N)~ (N ≤ 10^5)
Thử a = 1, 2, ... với lũy thừa nhanh mod N. Đúng 25/25 test.
Sub 2: Phân tích N, ~O(\sqrt{N})~
Gọi r là tích các ước nguyên tố của N; a phải là bội của r. Với p^e || N cần a \cdot v_p(a) \ge e; thử a = r, 2r, ... (điều kiện luôn đúng khi a ≥ 30). Đúng 25/25 test.
Chương trình hoàn chỉnh
main: N ≤ 10^5 gọi sub1, còn 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.
#include <bits/stdc++.h>
using namespace std;
long long N;
// Luy thua nhanh b^e mod m (m <= 10^9 nen tich khong tran so long long)
long long powmod(long long b, long long e, long long m) {
long long r = 1 % m;
b %= m;
while (e > 0) {
if (e & 1) r = r * b % m;
b = b * b % m;
e >>= 1;
}
return r;
}
// Sub 1: vet can. Thu lan luot a = 1, 2, ... kiem tra a^a co chia het cho N khong.
// Vi a = N luon thoa, vong lap dung chắc chắn sau toi da N buoc.
void sub1() {
for (long long a = 1;; a++)
if (powmod(a, a, N) == 0) {
cout << a << "\n";
return;
}
}
// Sub 2: phan tich N = p1^e1 * ... * pk^ek. a^a chia het cho p^e khi a*v_p(a) >= e.
// Moi p phai chia het a, nen a la boi cua r = p1*...*pk. Thu a = r, 2r, 3r, ... den khi thoa.
// (Khi a >= 30 thi luon thoa, vi e <= 30, nen vong lap ket thuc nhanh.)
void sub2() {
long long x = N;
vector<long long> pr;
vector<int> ex;
for (long long p = 2; p * p <= x; p++)
if (x % p == 0) {
int e = 0;
while (x % p == 0) {
x /= p;
e++;
}
pr.push_back(p);
ex.push_back(e);
}
if (x > 1) {
pr.push_back(x);
ex.push_back(1);
}
long long r = 1;
for (long long p : pr) r *= p;
for (long long k = 1;; k++) {
long long a = r * k;
bool ok = true;
for (size_t i = 0; i < pr.size() && ok; i++) {
long long v = 0, t = a;
while (t % pr[i] == 0) {
t /= pr[i];
v++;
}
if (a * v < ex[i]) ok = false;
}
if (ok) {
cout << a << "\n";
return;
}
}
}
int main() {
freopen("bai03.inp", "r", stdin);
freopen("bai03.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
if (N <= 100000) sub1();
else sub2();
return 0;
}
Bình luận