我遇到的问题是x=（16807 x k）%65536
ie 16807k∏x（型号65536）
我需要知道x来计算k。
我到目前为止最大的努力是一种野蛮的力量。有没有计算k的数学方法？
如果没有任何优化我目前的代码将不胜感激。
t = x;
while ( t += 15115 ) // 16807k = 65536n + x - this is the n
{
if (t%16807 == 0)
return t/16807;
}
return x;
编辑：更改+=为15115
最佳答案
奇数的乘法逆模是2的幂。
16807 mod 216的倒数是22039。
这意味着(16807 * 22039) % 65536 == 1，因此
(16807 * 22039 * x) % 65536 == x
以及
k = (22039 * x) % 65536
因此，您不必尝试任何操作，只需直接计算
k。