c - 找到满足模数的最小值

Question

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

即 16807k ≡ x (mod 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

Answer 1

奇数有乘法逆模 2 的幂。

16807 mod 2¹⁶ 的倒数是 22039。

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

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

和

k = (22039 * x) % 65536

因此您无需尝试任何操作，只需直接计算k即可。