求 $2^{2^{2….}} mod$ $p$的值 $(p≤10^7)$
tls题解
考虑欧拉定理， 当 $gcd(a,p)=1$ ，$a^{phi(p)} ≡ 1 (mod p )$
由此得出一个结论：
当$ x ≥ phi(p)$时
$$
a^x ≡ a^{x mod phi(p) + phi(p)} (mod p)
$$
令$f(p) = 2^{2^2…} mod p $, 则$f(1)=0。$
所以
$$
f(p)=2^{2^2.. mod phi(p) + phi(p)}(mod p)
$$
$$
=2^{f(phi(p))+phi(p)}(mod p)
$$
直接这样递推下去即可
最多只会递归 $log$ 次， 每次计算欧拉函数的复杂度为 $sqrt{p}$，总的复杂度为 $O(sqrt{p} log{p})$
如果有多组输入的话，应预处理
$phi ….. (phi(phi(p)))$的值
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
|
#define ll long long
using namespace std;
const int maxn = 1e5+100;
const int mod = 1e9+7;
char s[maxn];
int n,T;
int p[maxn];
ll (ll a, ll b, ll mod){
ll ans=1;
while(b){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
int phi(int n){
int ans=n;
for(int i=2;i*i<=n;i++){
if(n && n%i==0){
ans=ans/i*(i-1);
while(n%i==0)
n/=i;
}
}
if(n>1) ans=ans/n*(n-1);
return ans;
}
ll solve(ll p){
if(p==1) return 0;
ll k = phi(p);
return quick_pow(2, solve(k)+k, p);
}
int main(){
scanf("%d", &T);
while(T--){
scanf("%d", &n);
ll ans=solve(n);
printf("%lldn", ans);
}
return 0;
}
|
近期评论