是求(a^b) mod p
如果用暴力解法 O(b)
点击查看TLE代码c++
#include<iostream>
using namespace std;
int main()
{
int a,b,p;
long long res=1;
cin>>a>>b>>p;
while(b--)
res = res * a %p;
cout<<res<<endl;
}
所以就要用快速幂解法
如果b是二的幂；
就只需计算所有二的幂
点击查看样例b=128
(a^1) * (a^1) = (a^2)
(a^2) * (a^2) = (a^4)
(a^4) * (a^4) = (a^8)
(a^8) * (a^8) = (a^16)
(a^16) * (a^16) = (a^32)
(a^32) * (a^32) = (a^64)
(a^64) * (a^64) = (a^128)
只需计算7次
点击查看样例b=4096
(a^1) * (a^1) = (a^2)
(a^2) * (a^2) = (a^4)
(a^4) * (a^4) = (a^8)
(a^8) * (a^8) = (a^16)
(a^16) * (a^16) = (a^32)
(a^32) * (a^32) = (a^64)
(a^64) * (a^64) = (a^128)
(a^128) * (a^128) = (a^256)
(a^256) * (a^256) = (a^512)
(a^512) * (a^512) = (a^1024)
(a^1024) * (a^1024) = (a^2048)
(a^2048) * (a^2048) = (a^4096)
只需计算12次
就只需在b是二的幂的基础上新增一点点
步骤一
先把它看成二进制
步骤二
多乘二进制的一所代表的数
点击查看样例b=666
二进制是1010011010
(a^1) #0
(a^1) * (a^1) = (a^2) #1 需多乘
(a^2) * (a^2) = (a^4) #0
(a^4) * (a^4) = (a^8) #1 需多乘
(a^8) * (a^8) = (a^16) #1 需多乘
(a^16) * (a^16) = (a^32) #0
(a^32) * (a^32) = (a^64) #0
(a^64) * (a^64) = (a^128) #1 需多乘
(a^128) * (a^128) = (a^256) #0
(a^256) * (a^256) = (a^512) #1 需多乘
只需计算7次
以下是c++代码
long long counting(long long multiplier,int frequency,int mod){
int result = 1;
while(frequency){
if(frequency & 1){
res = (LL)result * multiplier % mod;
frequency >>= 1;
multiplier = (LL)multiplier * multiplier % mod;
}
}
return result;
}