欧拉降幂

欧拉降幂公式：

对于a^b mod c当b达到10^6时，就无法使用快速幂，需利用欧拉降幂公式

 

求解2^987654321%1000000的值

这么大的幂方，是快速幂算法无法求解的，这时我们将使用欧拉降幂算法，它的特点就是能够降低幂方的值且不影响最终结果

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
const int MAX=1000100;
LL qsm(LL a,LL b,LL mod)          //(a^b)%mod
{
    LL res=1;
    while(b>0)
    {
        if(b&1)
            res=(res%mod*a%mod)%mod;
        b>>=1;
        a=(a%mod*a%mod)%mod;
    }
    return res;
}

LL Euler(LL n)
{
    LL ans=1;
	for(int i=2;i*i<=n;i++)
    {
		if(n%i==0)
		{
			n/=i;
			ans*=(i-1);
			while(n%i==0)
			{
				n/=i;
				ans*=i;
			}
		}
	}
	if(n>1)
	  ans*=(n-1);
	return ans ;
}

//降幂函数
LL eulerDropPow(LL a,char b[],LL c)
{
    LL eulerNumbers=Euler(c);
    //存储降了之后的幂
    LL descendingPower=0;
    for(LL i=0,len=strlen(b);i<len;++i)
    {
        descendingPower=(descendingPower*10+b[i]-'0')%eulerNumbers;
    }
    descendingPower += eulerNumbers;
    return qsm(a,descendingPower,c);
}
int main() 
{
    LL a,c;
    char b[MAX];
    while(~scanf("%LLd%s%LLd",&a,b,&c))  //a的b次方对c取模
    {
        printf("%lld\n",eulerDropPow(a,b,c));
    }
    return 0;
}