我不想经历在 Windows 上安装 GMP 的噩梦。
我有两个数字A和B,unsigned long long
s,最多 10^10 左右的数量级,但即使在这样做时((A%M)*(B%M))%M
,我得到整数溢出。
是否有用于计算的自制函数(A*B)%M
对于更大的数字?
如果模数M
足够小于ULLONG_MAX
(如果它在 10^10 的区域内就是这种情况),您可以通过将其中一个因子分成两部分来分三步完成。我假设A < M
and B < M
, and M < 2^42
.
// split A into to parts
unsigned long long a1 = (A >> 21), a2 = A & ((1ull << 21) - 1);
unsigned long long temp = (a1 * B) % M; // doesn't overflow under the assumptions
temp = (temp << 21) % M; // this neither
temp += (a2*B) % M; // nor this
return temp % M;
对于较大的值,您可以将因子分成三部分,但如果模数变得非常接近ULLONG_MAX
它变得丑陋。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)