快速幂

mac2022-06-30 19

众所周知，用快速幂来计算加减乘除等问题，可以防止数据爆掉。

来看一下公式：(a+b)%p=(a%p+b%p)%p;(后面之所以要再%p是因为防(a%p+b%p）数据过大)

(a*b)%p=[(a%p)*(b%p)]%p;

(a-b)%p={[(a%p)-(b%p)]+p}%p;

下面我们来看第一种情况：(a+b)%p=(a%p+b%p)%p

int qsm(int a,int b) { int ans=1; while(b) { if(b%2==1) { ans*=a; } a=a*a; b/=2; } return ans; }

好了，那现在是第二种情况：(a*b)%p=[(a%p)*(b%p)]%p;

int qsm(int a,int b) { int ans=1; while(b) { if(b&1)//b&1意思是b%2=1 { ans=ans*a%p; } a=a*a%p; b>>=2;//意思相当于b/=2; } return ans; }

第三种情况和第二种情况类似，这里不予解释，大家可以自我思考。

转载于:https://www.cnblogs.com/RootVount/p/10022302.html