大数乘法的模
这个问题在这里已经有了答案：
这里的基本思想是首先定义一个非溢出的addmod函数，它在算法中利用负数。 然后使用位操作定义timesmod 。 时间复杂度是O(N) ，其中N是使用的位数（在这种情况下是64）。
#include <iostream>
using namespace std;
typedef long long BigInt; // must be signed, to detect overflow
BigInt A = 0x7fffffffffffff01;
BigInt B = 0x7fffffffffffff02;
BigInt M = 0x7fffffffffffff03;
// For simplicity it is assumed x, y, and m are all positive.
BigInt addmod( BigInt x, BigInt y, BigInt m )
{
x %= m;
y %= m;
BigInt sum = x-m+y; // -m <= sum < m-1
return sum < 0 ? sum + m : sum;
}
BigInt timesmod( BigInt x, BigInt y, BigInt m )
{
x %= m;
y %= m;
BigInt a = x < y ? x : y; // min
BigInt b = x < y ? y : x; // max
BigInt product = 0;
for (; a != 0; a >>= 1, b = addmod(b,b,m) )
if (a&1) product = addmod(product,b,m);
return product;
}
int main()
{
cout << "A = " << A << endl;
cout << "B = " << B << endl;
cout << "M = " << M << endl;
cout << "A*B mod M = " << timesmod(A,B,M) << endl;
return 0;
}
输出：
A = 9223372036854775553
B = 9223372036854775554
M = 9223372036854775555
A*B mod M = 2
这很容易证实，因为A=-2和B=-1 mod M
注意：此代码未优化。
我现在没有时间回答这个问题，所以我会给一个指针，稍后再回来编辑这个答案。 在你喜欢的算法教科书（或搜索引擎）中查找“Schrage乘法”。 基本思想是将A和B分成几块，分别处理这些部分，然后合并这些部分以完成计算。
我认为你可以将128位产品分成两部分（高64位和低64位），并减少每个模的p。 假设p约为4^k ，那么可以通过除以hi64 / (p>>k)来大致计算出该数字中有多少p。 这应该给你关于正确答案的k-1位。 从整体上减去许多p ，现在hi64的位数减少了k-1 。 再次这样做，但计算(hi64 << k-1) / (p >> k) 。 然后再做一次，计算(hi64 << k+k-2) / (p >> k) 。
施拉格的诡计，由另一张海报提出，听起来像是一个更好的交易，但我不明白。 希望那张海报能够回复并完成他的回答！
链接地址: http://www.djcxy.com/p/18279.html