隐藏
各种快速乘黑科技 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

各种快速乘黑科技

方法一

沿用快速幂的方法,将乘法改为加法,时间复杂度$O(\log b)$

1
2
3
4
5
LL Quick_Mul(LL a,LL b,LL p) {
LL sum=0;
for(; b; b>>=1,a=(a+a)%p)if(b&1)sum=(sum+a)%p;
return sum;
}

方法二

利用乘法分配律将乘数分为两部分依次累加进入答案。
此方法要求$p\lt2^{32}$,否则依然会溢出。

1
2
3
4
5
6
const LL LIMIT=1e6;

LL Quick_Mul(LL a,LL b,LL p) {
LL a1=a/LIMIT,a2=a%LIMIT,b1=b/LIMIT,b2=b%LIMIT;
return ((((a1*b1%p*LIMIT%p*LIMIT%p)+(a1*b2%p*LIMIT%p))%p+(a2*b1%p*LIMIT%p))%p+(a2*b2%p))%p;
}

方法三

暴力出奇迹!
此方法要求平台支持__int128

1
2
3
LL Quick_Mul(__int128 a,__int128 b,__int128 p) {
return a*b%p;
}

方法四

转成long double进行运算。
缺点是可能会有精度问题。

1
2
3
4
5
LL Quick_Mul(LL a,LL b,LL p) {
LL tmp=(a*b-(LL)((long double)a/p*b+1e-8)*p);
if(tmp<0)return tmp+p;
else return tmp;
}

姥爷们赏瓶冰阔落吧~