写着自己看的题解
可以称的上快速幂的变化?
我们将a*b可以转换一下
a*b=a*(x0+x1+x2+x3+...+xn)=a*x0+a*x1+a*x2+a*x3+...+a*xn
那么我们只要让b拆分一下并且让x0,x1,x2,x3,xn都存在一定联系就好了
于是我们将b化为二进制并拆成2的次方数 比如b=13=1+4+8
这样我们将b的二进制从右到左叫为c0,c1,cn
比如 b=13 二进制 1011 c0=1 c1=1 c2=0 c3=1
b=2^0*c0+2^1*c1+2^2*c2+...+2^n*cn
那么a*bw为
a*b=a*c0*2^0+a*c1*2^1+a*c2*2^2+...+a*cn*2^n
c我们可以求算,同时我们发现a*2^1=a*2^0 *2 a*2^2=a*2^1*2
那么我们可以有
a*b=y0*c0+y1*c1+y2*c2+...+yn*cn
同时y(i)=y(i-1)*2
我们就可以进行快速的计算并且不会越界了
代码附上
#include<iostream>
using namespace std;
long long a,b,p,ans;
int main(){
cin>>a>>b>>p;
while(b>0)
{
if (b&1) ans=(ans+a)%p;//若c为1,则计算
b>>=1;//相当于b=b/2 在求c
a=a*2%p;因为a<=10^18所以a*2<=2*10^18在long long的范围内,不会越界
}
cout<<ans%p;
return 0;
}