[2019ICPC南京网络赛B题]super_log

题目链接
这道题的意思转化过来就是求$a^{a^{a^{a^{…}}}}mod \space m$(共b个a)的值。

这个题从比赛开始我就在看,一直看到比赛结束都没写出来,最后终于在晚些时候写出来了。

这道题并不是特别难的题,主要就是里面一些细节不好处理。这道题利用的算法就是欧拉定理,在求最底层的$a$的指数时,我们可以先求$a$的指数的指数,然后依次递归求每层的指数,在递归的过程中,可以利用欧拉降幂来简化指数。在这之前先需要了解以下扩展欧拉定理
$$
a^c=\begin{cases}
a^{c \space mod \space \phi(m)} \space \space \space \space \space \space \space \space gcd(a,m)=1 \\
a^c \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space gcd(a,m)\neq 1,c<\phi(m) \\
a^{c \space mod \space \phi(m)+\phi(m)} gcd(a,m)\neq 1 ,c\geq \phi(m)
\end{cases}
$$
由扩展欧拉定理我们就可以去递归求解了。首先要打一个欧拉函数的表,然后对于每一层,我们需要去计算它的指数是否大于$\phi(m)$,判断的方法就是暴力,然后就完了。

代码如下:

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=3000000+10;
ll phi[maxn],chk[maxn],tot,pri[maxn];
void getphi() {//欧拉函数打表
phi[1]=1;
for(int i=2;i<=2000000;i++) {
if(!chk[i]) {
pri[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&i*pri[j]<=2000000;j++) {
chk[i*pri[j]]=1;
if(i%pri[j]==0) {
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
else {
phi[i*pri[j]]=phi[i]*(pri[j]-1);
}
}
}
}
ll qp(ll a,ll b,ll mod){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
bool check(ll a,ll b,ll m) {//检查是否需要对指数进行添加
if(b==0) return 1>=m;
if(b==1) return a>=m;
ll q=a;
for(int i=0;i<b-1;i++){//这里暴力判断是否大于phi[m]
ll x=1;
for(int j=0;j<a;j++){
x*=q;
if(x>=m) return true;
}
q=x;
}
return false;
}
ll dfs(ll a,ll b,ll m){
if(m==1) return 0;//特判三种情况
if(b==0) return 1;
if(b==1) return a%m;
//递归求解
if(check(a,b-1,phi[m])) return qp(a,dfs(a,b-1,phi[m])+phi[m],m);
else return qp(a,dfs(a,b-1,phi[m]),m);
}
int main()
{
getphi();
int t;
scanf("%d",&t);
while(t--){
ll a,b,m;
scanf("%lld %lld %lld",&a,&b,&m);
printf("%lld\n",dfs(a,b,m)%m);
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------