#include <stdio.h> int qpow(int b, int e,int s)//快速幂 { int a = 1,c; for(int i=e;i;i>>=1)//简化计算次数将1,2,3,4……变成2^1,2^2,2^3,2^4…… { if(i&1) a=(long long)a * b % s; //i&1:按位与运算二进制1有8位数00000001,二进制i有XXXXXXXX若最后一个X为1则输出1否则为0相当于i%2==1 b=(long long)b*b%s; } return a; } int main() { char ch; int k; int i,b=0,a,n,m,s,ans; scanf("%d %d",&a,&m); a=a%m; ans=m; n=m; s=m; for(i=2;i*i<=n;i++)//查找 { if(n%i==0) { ans*=(i-1.0)/i;//定义公式 while(n%i==0) n/=i*1.0;//找出n的因数中与i互质的最大因数 } } if(n>1) ans*=(n-1)*1.0/n;//补充for循环中漏掉的质因数 int flag=0; getchar();//消除空格 while((ch = getchar()) >= '0' && ch <= '9') { b=b*10+(ch^'0');//将ch转化为整数类型 if(b>=ans)//判断选择扩展欧拉定理>=phi(m)部分还是<phi(m)部分 { flag=1; b=b%ans; } } if(flag==1) b+=ans; printf("%d",qpow(a,b,s)); return 0; }
扩展欧拉定理实战,今日份学习