题目链接
题目大意：求 222… (无限个2) %p的值
题解：发现自己学了假的扩展欧拉定理……就是要求底数和模数互质的那个……
根据真扩展欧拉定理
an≡an%φ(p)+φ(p)(modp)(n≥φ(p))
这个不要求a，p互质
那么递归做下去，当p=1时这个式子为0
递归层数显然是log p的，欧拉函数暴力求就可以了
我的收获：23333
#include <bits/stdc++.h> using namespace std; typedef long long ll; int p,T; int Phi(int x){ int ret=x; for(int i=2,lim=sqrt(x)+1;i<lim;i++) if(!(x%i)){ ret-=ret/i; while(!(x%i)) x/=i; } return x>1?ret-ret/x:ret; } ll pw(ll a,ll n,ll P){ ll ans=1; for(;n;n>>=1,a=a*a%P) if(n&1) ans=ans*a%P; return ans; } ll f(int x){ if(x==1) return 0; int phi=Phi(x); return pw(2,f(phi)+phi,x); } int main() { scanf("%d",&T); while(T--) scanf("%d",&p),printf("%lld\n",f(p)); return 0; }