描述
输入b，p，k的值，求b^p mod k的值。其中b，p，k×k为长整型数。

格式
输入格式
输入b，p，k的值。

输出格式
求b^p mod k的值。

样例
输入样例
2 10 9
输出样例
2^10 mod 9=7

思路

1、把p转化成二进制形式存入数组中，如10=1010

十进制转二进制：取模取余即可

while(n!=0){
        a[cnt]=n%2;
        n/=2;
        cnt++;
    }

2、w,result

二进制为4位数，进行四轮运算

第一轮：w=b%k，二进制为0，result不做改变  w=2,result=1

第二轮：w=w*w%k，二进制为1，result=result*w%k;   w=4,result=4

第三轮：w=w*w%k，二进制为0，result不做改变  w=7,result=4

第四轮：w=w*w%k,二进制为1，result=result*w%k;  w=4,result=7

代码如下

#include<iostream>
using namespace std;
int main(){long long b,p,k;cin>>b;cin>>p;cin>>k;int i=0,cnt=0,a[35]={};long long n=p;while(n!=0){a[cnt]=n%2;n/=2;cnt++;}long long w;int result=1;if(p==0){result=1%k;}else{for(i=0;i<cnt;i++){if(i==0)w=b%k;else w=w*w%k;if(a[i])result=result*w%k;}}cout<<b<<"^"<<p<<" mod "<<k<<"="<<result;
}