找到满足模数的最小值

Question

我遇到的问题是x =(16807 xk)%65536

即16807k≡x(mod 65536)

我需要计算k知道x.到目前为止,我的最大努力是一种蛮力.有没有数学方法来计算k？如果不是我的当前代码的任何优化将不胜感激.

t = x;
while ( t += 15115 ) // 16807k = 65536n + x - this is the n
{
    if (t%16807 == 0)
    return t/16807;
}
return x;

编辑:更改+ =到15115

Answer 1

奇数具有乘法逆模,其幂为2.

16807 mod 2 ¹⁶的倒数是22039.

这意味着(16807 * 22039) % 65536 == 1,因此,那

(16807 * 22039 * x) % 65536 == x

和

k = (22039 * x) % 65536

所以你不必尝试任何东西,你可以直接计算k.