1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
| #include <iostream> #include <unordered_map> #include <functional>
using i64 = long long; const int mod = 998244353;
i64 quickPow(i64 x, i64 n, i64 mod) { i64 res = 1; while (n) { if (n & 1) res = (__int128_t)res * x % mod; x = (__int128_t)x * x % mod; n >>= 1; }
return res; }
bool millerRabin(i64 n, int test_times = 8) { if (n < 3 || n % 2 == 0) return n == 2; i64 u = n - 1; int t = 0; while (!(u & 1)) { u >>= 1; t++; } for (int i = 0; i < test_times; i++) { i64 a = std::rand() % (n - 2) + 2; i64 v = quickPow(a, u, n); if (v == 1) continue; int s; for (s = 0; s < t; s++) { if (v == n - 1) break; v = (__int128_t)v * v % n; } if (s == t) return false; }
return true; }
i64 gcd(i64 x, i64 y) { return y == 0 ? x : gcd(y, x % y); }
i64 Pollard_Rho(i64 x) { i64 s = 0, t = 0; i64 c = (i64)std::rand() % (x - 1) + 1; int step = 0, goal = 1; i64 val = 1; for (goal = 1; ; goal <<= 1, s = t, val = 1) { for (step = 1; step <= goal; step++) { t = ((__int128_t)t * t + c) % x; val = (__int128_t)val * std::abs(t - s) % x; if (step % 127 == 0) { i64 d = gcd(val, x); if (d > 1) return d; } } i64 d = gcd(val, x); if (d > 1) return d; } }
i64 solve() { i64 x; std::cin >> x; std::unordered_map<i64, int> res; std::function<void(i64)> fac = [&res, &fac](i64 n) { if (n < 2) return; if (millerRabin(n)) { res[n]++; return; } i64 p = n; while (p >= n) p = Pollard_Rho(n); fac(p), fac(n / p); }; fac(x); if (res.size() == 1) { return res.begin()->first; } else { return 1; } }
int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int numTest; std::cin >> numTest; for (int i = 0; i < numTest; i++) { std::cout << solve() % mod << " \n"[i == numTest - 1]; }
return 0; }
|