C++ 快速幂取模+大数相乘取模

2019-04-13 15:47发布

站内文章 / 模拟电子
9390 0 1598
ll qmul(ll x, ll y, ll mod) // 乘法防止溢出， 如果p * p不爆LL的话可以直接乘； O(1)乘法或者转化成二进制加法(快速加) { ll ret = 0; while(y) { if(y & 1) ret = (ret + x) % mod; x = x * 2 % mod; y >>= 1; } return ret; } ll qpow(ll a, ll n, ll mod) { ll ret = 1; while(n) { if(n & 1) ret = qmul(ret, a, mod); a = qmul(a, a, mod); n >>= 1; } return ret; } 当几个数连续乘最后取模时，可以将每个数字先取模，最后再取模，即%对于*具有结合律。但是如果当用来取模的数本身就很大，采取上述方法就不行了。这个时候可以借鉴快速幂取模的方法，来达到大数相乘取模的效果。

热门文章