快速幂运用分治思想

显然有：

每次根据该公式分治计算即可。

#include<iostream>
#include<cstdio>

using namespace std;

long long int b,p,k,ans=1;
int main()
{
    scanf("%lld%lld%lld",&b,&p,&k);
//  printf("%lld^%lld mod %lld=",b,p,k);
    if(k==1){
        puts("0");
        return 0;
    }
    while(p>0)
    {
        if(p&1) ans=ans*b%k;
        b=b*b%k;
        p>>=1;
    }
    printf("%lld\n",ans);
    return 0;
}