ACM技巧 - O(1)快速乘（玄学） 总结

ACM技巧 - O(1)快速乘（玄学） 总结

ll fast_mult(ll a,ll b,ll mod) { return (a*b - (ll)((long double)a/mod*b)*mod+mod)%mod;}

参考​

注意事项：

double可能会挂，最好long double。u,v>=p可能会挂，必要时先%p。用浮点数算出u*v/p的值时事实上允许了±1的误差，因此可能出现负数，所以必须+p再%p。因此理论上不需要+eps。

还有一种模板：

inline ll fast_mult(ll x,ll y,ll mod) { ll tmp=(x*y-(ll)((long double)x/mod*y+1.0e-8)*mod); return tmp<0 ? tmp+mod : tmp;}

另：

ll n,k,p;ll kre(ll a,ll b){ a=a%p; b=b%p; return ((a*b-(ll)(((double)a*b+0.5)/p)*p)+p)%p;}ll kru(ll a,ll b){ ll ret=1; while(b){ if(b&1){ ret=kre(ret,a)%p; b--; } b/=2; a=kre(a,a)%p; } return ret;}

参考​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。