1326：【例7.5】 取余运算（mod）

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

【输入】

【输出】

【输入样例】

2 10 9

【输出样例】

2^10 mod 9=7

 解析：快速幂算法，可以使用递归，详见代码：

#include <bits/stdc++.h>
using namespace std;
long long f(int x,int y,int z){
    if (y==0) return 1;
    long long p=f(x,y/2,z);
    if (y%2==1){
        return p*p%z*x%z;
    }else{
        return p*p%z;
    }
}
int main() {
    long long b,p,k;
    cin>>b>>p>>k;
    cout<<b<<"^"<<p<<" mod "<<k<<"=";
    cout<<f(b,p,k);
    return 0;
}

也可以使用递推，详见代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long b,p,k;
    cin>>b>>p>>k;
    cout<<b<<"^"<<p<<" mod "<<k<<"=";
    long long ans=1;
    long long m=b;
    while(p>0){
        if (p%2==1){
            ans*=m;
            ans%=k;
        }
        p/=2;
        m*=m;
        m%=k;
    }
    cout<<ans;
    return 0;
}