algorithm - 如何有效解决涉及 'modulo' 操作的编码问题？

Question

我们得到一个整数 'N' 。我们可以选择 (1 到 z) 范围内的任意 2 个数字(a 和 b)。 L 的值由下式给出，

L = Max(( (N%a) %b) %N)  

我们必须计算给定值 'L' 的 (a,b) 对的数量。 我知道蛮力，一个，O(n²) 解决方案。 有没有更有效的方法来解决这个问题？!

Answer 1

我能破译的唯一方法Max(( (N%a) %b) %N)是最大值接管了所有 a, b对。如果我错了，请忽略其余部分。

万一z > N/2 :

• 首先，观察如果两个a和 b大于 N , 然后 (N%a) % b产量 N , 所以 (N%a) %b) %N产生 1，这是不令人满意的小。因此至少其中之一应小于 N .

• 其次，观察(更好的是证明)N % a 的最大值当 a 时实现是N/2 + 1对于偶数 N , 和 (N + 1)/2对于奇数(重要说明:它是 N 之后下一个 2 的倍数的一半)。称之为 maximizer .

• 最后，观察任何 b大于该模数使其保持不变。证明这确实是所需的最大值。

现在你有足够的事实来有效地提出一个单行程序(不要忘记 a > N, b = maximizer 案例)。

同样的逻辑适用于 z < N/2 .找到最大化器有点棘手，但在 O(1) 中仍然可行(请参阅上面的重要说明)。