洛谷P1226 【模板】快速幂||取余运算

题目描述

给你三个整数 b,p,kb,p,k，求 b^p bmod kbpmodk。

输入格式

一行三个整数 b,p,kb,p,k

输出格式

输出 b^p mod k=s

ss 为运算结果

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

【样例解释】
2^{10} = 1024210=1024，1024 bmod 9 = 71024mod9=7。

【数据范围】
对于 100%100% 的数据，0le b,p,k < 2^{31}0≤b,p,k<231。

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long int
ll power(ll a,ll b,ll p);
int main()
{
    ll b,p,k;
    while(cin>>b>>p>>k)
    {
        cout<<b<<"^"<<p<<" mod "<<k<<"="<<power(b,p,k)<<endl;
    }
}
ll power(ll a,ll b,ll p)
{
    int ans=1%p;
    for(;b;b>>=1)    //通过b>>=1舍弃最低位，通过b&1判断最低位的值 
    {
        if(b&1)
        {
            ans=(ll)ans*a%p;    
        } 
        a=(ll)a*a%p;
    }
    return ans;    
}