@[cloudemakers](/user/550074) 递归出问题了
by yszkddzyh @ 2023-09-23 18:16:01
应该是solve函数递归太多导致堆栈溢出
by ioshift @ 2023-09-23 18:18:36
@[ioshift](/user/302912) 这就是题解做法啊?怎么会呢
by cloudemakers @ 2023-09-23 18:34:03
@[cloudemakers](/user/550074) 好像是 phi 先乘后除导致溢出了
by Michaellg @ 2023-09-23 18:56:20
@[Michaellg](/user/670677) 好像是的,这样就AC了(加了几个__int128):
```cpp
#include<bits/stdc++.h>
using namespace std;
int t,p,ret,a,i,ph;
int POW(int b,int mod){
ret=1,a=2;
while (b){
if (b&1) ret=((__int128)ret%mod*a%mod)%mod;
a=((__int128)a%mod*a%mod)%mod;
b>>=1;
}
return ret;
}
int phi(int op){
ret=op;
for (i=2;i<=sqrt(op);i++){
if (op%i==0){
while (op%i==0) op/=i;
ret=(__int128)ret*(i-1)/i;
}
}
if (op>1) ret=(__int128)ret*(op-1)/op;
return ret;
}
int solve(int m){
if (m==1||m==0) return 0;
int ph=phi(m);
return POW(solve(ph)+ph,m);
}
int main(){
cin>>t;
while (t--){
scanf("%d",&p);
printf("%d\n",solve(p));
}
return 0;
}
```
by ioshift @ 2023-09-23 19:08:04
@[Michaellg](/user/670677) 哦哦多谢!~~不开long long见祖宗~~
by cloudemakers @ 2023-09-23 19:45:12