快速幂与模运算

快速幂与模运算

 

题目描述

给你三个整数 b，p，k，求bp mod k的值。

输入格式

输入只有一行三个整数，分别代表b，p，k。

输出格式

输出一行一个字符串，格式：b^p mod k=s

其中 b，p，k 分别为题目给定的值，s为运算结果。

样例输入

2 10 9

样例输出

2^10 mod 9=7

问题提示

【样例解释】

210 = 1024，1024 mod 9 = 7 。

【数据范围】

对于 100% 的数据，0≤b,p,k<231，其中k不为0。

代码如下：

#include
using namespace std;
long long pow(long long a,long long b,long long p){
    long long ret=1%p;
    while(b){
        if(b&1) ret=ret*a%p;
        b>>=1;a=a*a%p;
    }
    return ret;
}
int main(){
    long long a,b,p;cin>>a>>b>>p;
    cout<