扩展欧拉定理（应用）4@亿万星辰 洛谷P5091

#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;
}