我怎样才能有效地解决这个编码问题涉及的“模”的操作？

Question

我们将得到一个整数“N”。我们可以选择在范围内的任何数字2（a和b）（1到z）。 L的值由下式给出，

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

我们来计算对数（A，B），其得到（S）的值“L”。我知道蛮力，一，O（n2）的解决方案。有没有办法解决这个问题的任何更有效的方法？

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的最大值达到（重要提示：这是2 N之后的下一个倍数的一半）。说它是maximizer。
• 最后，观察到任何b比模更大离开它不变。证明这确实是需要的最大值。

现在，你有足够的事实拿出有效的一行程序（不要忘了a > N, b = maximizer情况下）。

同样的逻辑也适用于z < N/2。寻找最大化是有点棘手，但在O(1)仍有可能（见上文的重要说明）。