Hướng dẫn giải của Số Cool (Đề THCS Phú Thọ 2023-2024)
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ập ~A~ gồm các ước nguyên tố ~d~ của ~n~ thỏa mãn ~1 < d < n~. Cool(~n~) là tích của ~(3^d + d)~ theo mọi ~d \in A~ (nếu ~A~ rỗng thì bằng 1). Cần in ra Cool(~n~) chia lấy dư cho ~20232024~. Lưu ý: mọi phép nhân đều lấy dư ngay sau mỗi bước; luỹ thừa ~3^d~ tính bằng lũy thừa nhanh theo modulo để không bị quá giờ với ~d~ lớn.
Sub 1: Vét cạn với kiểm tra nguyên tố chậm — ~O(n^2)~, dùng khi ~n < 10^3~
Thử mọi ~d = 2, \ldots, n-1~. Nếu ~d~ là ước của ~n~ thì kiểm tra nguyên tố bằng cách thử mọi ước của ~d~ rồi nhân vào tích. Nếu chỉ nộp sub này: đúng 18/20 test (đúng hết các test trong miền, 2 test lớn bị quá giờ).
Sub 2: Thử ước đến căn bậc hai — ~O(n \sqrt{n})~, dùng khi ~n < 10^6~
Giữ nguyên cách duyệt các ước, nhưng kiểm tra nguyên tố chỉ thử đến ~d \cdot d \le x~. Điều này giảm mạnh số phép chia. Nếu chỉ nộp sub này: đúng 18/20 test (2 test có ~n \ge 10^6~ vẫn quá giờ).
Sub 3: Phân tích thừa số bằng thử đến căn bậc hai — ~O(\sqrt{n})~, dùng cho ~n \le 10^9~
Chia ~n~ lần lượt cho các ~p~ từ 2 đến ~\sqrt{n}~; mỗi ước nguyên tố ~p~ tìm được thì bỏ hết các lũy thừa của ~p~. Phần còn lại sau khi chia (nếu lớn hơn 1) là một số nguyên tố lớn. Chỉ nhân những ước nguyên tố ~p < n~. Bẫy cần chú ý: khi ~n~ là số nguyên tố thì ~A~ rỗng, kết quả là 1; không được nhân ~n~ vào tích vì ~d < n~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc ~n~. Nếu ~n < 10^3~ gọi sub1; nếu ~n < 10^6~ gọi sub2; còn lại gọi sub3.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 20232024;
long long n;
// Luy thua nhanh: base^e mod MOD
long long powmod(long long base, long long e) {
long long res = 1 % MOD;
base %= MOD;
while (e > 0) {
if (e & 1) res = res * base % MOD;
base = base * base % MOD;
e >>= 1;
}
return res;
}
// Tinh (3^d + d) mod MOD
long long factorOf(long long d) {
return (powmod(3, d) + d % MOD) % MOD;
}
// Kiem tra nguyen to bang cach thu moi uoc (cham)
bool isPrimeSlow(long long x) {
if (x < 2) return false;
for (long long d = 2; d < x; d++)
if (x % d == 0) return false;
return true;
}
// Kiem tra nguyen to bang cach thu uoc den can bac hai
bool isPrimeFast(long long x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
// Sub 1: vet can O(n * n) - thu moi d tu 2 den n-1, neu d la uoc nguyen to thi nhan vao tich.
void sub1() {
long long ans = 1 % MOD;
for (long long d = 2; d < n; d++)
if (n % d == 0 && isPrimeSlow(d))
ans = ans * factorOf(d) % MOD;
cout << ans << "\n";
}
// Sub 2: thu moi d tu 2 den n-1 nhung kiem tra nguyen to bang can bac hai
void sub2() {
long long ans = 1 % MOD;
for (long long d = 2; d < n; d++)
if (n % d == 0 && isPrimeFast(d))
ans = ans * factorOf(d) % MOD;
cout << ans << "\n";
}
// Sub 3: phan tich n thanh thua so nguyen to bang thu chia den can bac hai (O(sqrt n))
void sub3() {
long long ans = 1 % MOD;
long long m = n;
vector<long long> primes;
for (long long p = 2; p * p <= m; p++) {
if (m % p == 0) {
primes.push_back(p);
while (m % p == 0) m /= p; // bo het cac luy thua cua p
}
}
if (m > 1) primes.push_back(m); // phan con lai la mot so nguyen to lon
for (long long p : primes)
if (p > 1 && p < n) // chi lay uoc nguyen to lon hon 1 va nho hon n
ans = ans * factorOf(p) % MOD;
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
if (n < 1000) sub1(); // subtask 1
else if (n < 1000000) sub2(); // subtask 2
else sub3(); // subtask 3
return 0;
}
Bình luận