[Description]

求值2222 mod p2^{2^{2^{2…∞}}}\ mod\ p

[Solution]

不要被无限个2吓到了,这一题有一些有趣的性质可以发掘的。
这里介绍两个解法。

Solution 1

我们温习一下欧拉定理:

anan mod φ(p) mod p        (gcd(n,p)=1)a^n≡a^{n\ mod\ φ(p)}\ mod\ p\ \ \ \ \ \ \ \ (gcd(n,p)=1)

和它的推广:

anan mod φ(p)+φ(p) mod pa^n≡a^{n\ mod\ φ(p)+φ(p)}\ mod\ p

我们发现,这题的n,p并不一定互素啊,怎么办呢?我们可以让他们强行互素。
利用公式:

an mod aky=ak(ank mod y)a^n\ mod\ a^k⋅y=a^k⋅(a^{n−k}\ mod\ y)

我们把原题中的pp分为2k+y2^k+y
所以原式化为

2k(2(222k) mod y)2^k⋅(2^{(2^{2^{2…∞}}−k)}\ mod\ y)

此时y是奇数,和指数互质了!然后就可以愉快地使用欧拉定理–原式化为

2k(2(222k) mod φ(y)+φ(y) mod y)2^k⋅(2^{(2^{2^{2…∞}}−k)\ mod\ φ(y)+φ(y)}\ mod\ y)

我们发现中间的指数一部分又与原问题相似,于是想到可以递归求解。
那边界是什么呢?我们发现,φ(y)会不断缩小,而且每次至少会除去一个2,所以递归的深度最多为log2§,当y=1时,返回0即可。

需要事先筛好phi值或者直接需要的时候根号时间计算求解。

复杂度O(p+log2(p))O(p+log_2(p))–线性筛O(log2(p)sqrt(p))O(log_2(p)*sqrt(p))–直接计算。
实践过程中第二种方法远远快于第一种。

Solution 2

还是根据公式

anan mod φ(p)+φ(p) mod pa^n≡a^{n\ mod\ φ(p)+φ(p)}\ mod\ p

设答案为f§,有

f(p)=2222modp=2(222) mod φ(p)+φ(p) mod p=2f(φ(p))+φ(p) mod pf(p)=2^{2^{2^{2…∞}}} mod p \\ =2^{(2^{2^{2…∞}})\ mod\ φ(p)+φ(p)}\ mod\ p \\ =2^{f(φ(p))+φ(p)}\ mod\ p

同样递归求解即可,复杂度同第一个解。

[Code]

给出两种解法的代码,第一种用的线性筛,第二种直接求解。

Code 1

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
#include<cstdio>

typedef long long ll;
const int maxn=10000001;

int phi[maxn]={0,1};
void MakePhiList(){
for(int i=2;i<maxn;i++) if(!phi[i])
for(int j=i;j<maxn;j+=i){
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}

ll pow(ll a,int n,int p){
ll ans=1;
while(n) {
if(n&1) ans=ans*a%p;
a=a*a%p; n>>=1;
}
return ans;
}


ll f(int x){
if(x==1) return 0;
int k=0; while(!(x%2)) x/=2,k++;
return pow(2,(f(phi[x])%phi[x]-k%phi[x]+phi[x])%phi[x]+phi[x],x)<<k;
}

int main(){
MakePhiList();
int kase; scanf("%d",&kase);
while(kase--){
int x; scanf("%d",&x);
printf("%lld\n",f(x));
}
return 0;
}

Code 2

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
#include<cmath>
#include<cstdio>

typedef long long ll;

int Phi(int x){
int ans=x;
for(int i=2,lim=sqrt(x)+1;i<lim;i++) if(!(x%i)){
ans-=ans/i;
while(!(x%i)) x/=i;
}
return x>1?ans-ans/x:ans;
}

ll pow(ll a,ll n,ll p){
ll ans=1;
while(n){
if(n&1) ans=ans*a%p;
a=a*a%p; n>>=1;
}
return ans;
}

ll f(int x){
if(x==1) return 0;
int phi=Phi(x);
return pow(2,f(phi)+phi,x);
}

int main(){
int kase; scanf("%d",&kase);
while(kase--){
int x; scanf("%d",&x);
printf("%lld\n",f(x));
}
return 0;
}

Comment