欧拉降幂公式
- #include<cmath>
- #include<cstdio>
- using namespace std;
- int get_phi(int p)
- {
- int phi=p;
- int m=sqrt(p);
- for(int i=2;i<=m;++i)
- if(p%i==0)
- {
- phi=phi/i*(i-1);
- while(p%i==0) p/=i;
- }
- if(p>1) phi=phi/p*(p-1);
- return phi;
- }
- int Pow(int a,int b,int p)
- {
- int res=1;
- for(;b;a=1LL*a*a%p,b>>=1)
- if(b&1) res=1LL*res*a%p;
- return res;
- }
- int f(int p)
- {
- if(p==1) return 0;
- int phi=get_phi(p);
- return Pow(2,f(phi)+phi,p);
- }
- int main()
- {
- int T,P;
- scanf("%d",&T);
- while(T--)
- {
- scanf("%d",&P);
- printf("%d\n",f(P));
- }
- }
来源: http://www.bubuko.com/infodetail-2519603.html