快速乘法取模

2019-04-13 12:38发布

站内文章 / 模拟电子
16227 0 964
如果让你计算66666666666666666*555555555555555555（17位），这样一个结果对33333333333333333取模你会怎么计算呢，像这样2个long long型的整数相乘肯定会爆掉，所以我们引入一个快速乘法来计算，这个算法的原理是怎样的呢，其实和快速幂差不多。例如：5(a)*8(b) = 5*2*2*2，5*9 = 5*3*3 = 5*(2+1)*(2+1)，就是利用了这样的计算原理，就把一个数不断除以2，一个数不断乘以2，如果b%2 == 1的话就在加一个a，因为类似于5*3啊，5+5*2对吧。。。实现代码：LL work(LL a, LL b, LL mod) { LL ans = 0; while(b) { if(b&1) { ans += a; ans %= mod; } a *= 2; a %= mod; b /= 2; } return ans; }

热门文章