You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
46 lines
1.0 KiB
46 lines
1.0 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
// https://blog.csdn.net/skywalkert/article/details/43955611
|
|
// https://www.cnblogs.com/shuguangzw/p/5697183.html
|
|
// 指数循环节问题
|
|
// https://blog.csdn.net/acdreamers/article/details/8236942
|
|
map<int, int> f;
|
|
int pow(int x, int k, int p) {
|
|
int ret = 1;
|
|
while (k) {
|
|
if (k & 1)
|
|
ret = (long long)ret * x % p;
|
|
x = (long long)x * x % p;
|
|
k >>= 1;
|
|
}
|
|
return ret;
|
|
}
|
|
int phi(int x) {
|
|
int ret = x;
|
|
for (int i = 2; i * i <= x; ++i)
|
|
if (x % i == 0) {
|
|
ret -= ret / i;
|
|
while (x % i == 0)
|
|
x /= i;
|
|
}
|
|
if (x > 1)
|
|
ret -= ret / x;
|
|
return ret;
|
|
}
|
|
int F(int x) {
|
|
if (f.count(x))
|
|
return f[x];
|
|
int p = phi(x);
|
|
return f[x] = pow(2, F(p) + p, x);
|
|
}
|
|
int main() {
|
|
int t, n;
|
|
scanf("%d", &t);
|
|
f[1] = 0;
|
|
while (t--) {
|
|
scanf("%d", &n);
|
|
printf("%d\n", F(n));
|
|
}
|
|
return 0;
|
|
} |