一.快速幂
描述
求 a 的 b 次方对 p 取模的值,其中 1≤a,b,p≤10^9
输入格式
三个用空格隔开的整数a,b和p。
输出格式
一个整数,表示a^b mod p的值。
样例输入
2 3 9
样例输出
8
二.快速乘
描述
求 a 乘 b 对 p 取模的值,其中 1≤a,b,p≤10^18。
输入格式
第一行a,第二行b,第三行p。
输出格式
一个整数,表示a*b mod p的值。
样例输入
2 3 9
样例输出
6
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
///b&1取出b二进制位下表示的最低位
///b>>1舍弃最低位
ll quick_mul(ll a,ll b,ll p)///计算a*b %p
{ll ans=0;for(;b;b>>=1){if(b&1) ans=(ans+a)%p ;a=a*2%p;}return ans;
}
ll quick_qow(ll a,ll b,ll p)///计算a^b %p
{ll ans=1%p;///ans不能为1,b为0,p为1的情况不成立for(;b;b>>=1){if(b&1) ans=(ans*a)%p ;a=a*a%p ;}return ans;
}
int main()
{ll a,b,k,ans;cin>>a>>b>>k;cout<<quick_qow(a,b,k);return 0;
}