题目

打个表发现当 n = 时答案为 p ，否则为 1 ，然后套板子。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>using namespace std;#define int long long
using i64 = long long;const int N = 1000100;
const i64 inf = 1e18 + 1;
const int mod = 998244353;int n, m, primes[N], cnt;
bool st[N];void init(int n = 1000010) {for (int i = 2; i <= n; i++) {if (!st[i]) primes[cnt++] = i;for (int j = 0; j < cnt && primes[j] * i <= n; j++) {st[i * primes[j]] = true;    if (i % primes[j] == 0) break;}}
}i64 sqrt(i64 x) {i64 l = 0, r = 1e9;while (l < r) {i64 mid = l + r + 1 >> 1;if (1ll * mid * mid <= x) l = mid;else r = mid - 1;}return l;
}bool is_prime(i64 n) {if (n == 1) return 0;for (i64 i = 2; i <= n / i; i++)if (n % i == 0) return false;return 1;
}long long quick_pow(long long x, long long p, long long mod) {  // 快速幂long long ans = 1;while (p) {if (p & 1) ans = (__int128)ans * x % mod;x = (__int128)x * x % mod;p >>= 1;}return ans;
}bool Miller_Rabin(long long p) {  // 判断素数if (p < 2) return 0;if (p == 2) return 1;if (p == 3) return 1;long long d = p - 1, r = 0;while (!(d & 1)) ++r, d >>= 1;  // 将d处理为奇数for (long long k = 0; k < 10; ++k) {long long a = rand() % (p - 2) + 2;long long x = quick_pow(a, d, p);if (x == 1 || x == p - 1) continue;for (int i = 0; i < r - 1; ++i) {x = (__int128)x * x % p;if (x == p - 1) break;}if (x != p - 1) return 0;}return 1;
}signed main() {init();int T;cin >> T;while (T--) {srand((unsigned)time(NULL));i64 n;cin >> n;if (n == 1) {std::cout << 1 << " ";continue;}if (Miller_Rabin(n)) {std::cout << n % mod << " ";continue;}i64 res = inf;i64 t = sqrt(n);if (t * t == n) {  if (is_prime(t)) {cout << t % mod << ' ';continue;}}for (int i = 0; i < cnt; i++) {i64 p = primes[i];if (n % p == 0) {i64 tmp = n;while (tmp % p == 0) tmp /= p;if (tmp == 1) res = p;else res = 1;}}if (res == inf) res = 1;cout << res % mod << ' ';}exit(0);
}