P1226 【模板】快速幂题解

题目

给你三个整数a,b,p，求 mod p。

输入输出格式

输入格式

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

输出格式

输出一行一个字符串a^b mod p=s，其中a,b,p分别为题目给定的值，s为运算结果。

输入输出样例

输入样例

2 10 9

输出样例

2^10 mod 9=7

代码

#include<iostream>
using namespace std;
int a,b,p;
int main(){cin>>a>>b>>p;int ans=1,base=a;int m=b;while(b>0){if(b&1){ans=(ans%p)*(base%p);}base=(base%p)*(base%p);b>>=1;}ans=ans%p;cout<<a<<"^"<<m<<" "<<"mod"<<" "<<p<<"="<<ans;return 0;
}