BZOJ 3884

Posted on | In ,

求 $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
#include<bits/stdc++.h>
#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 quick_pow(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("%lld\n", ans);
    }
    return 0;
}