如何有效地解决这个涉及“模数”运算的编码问题？
如何有效地解决这个涉及“模数”运算的编码问题？
提问于 2019-01-07 01:06:46
我们给出一个整数'N'。我们可以在范围（1到z）中选择任意2个数字（a和b）。L的值由下式给出，
L = Max(( (N%a) %b) %N)
我们必须计算给出（L）值的对的数量（a，b）。我知道一个简单粗暴的办法，一，O（n ^ 2）解决方案。有没有更有效的方法来解决这个问题？！谢谢
回答 1
Stack Overflow用户
发布于 2019-01-07 10:39:22
我可以破译的唯一方法：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。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/-100008951
复制相关文章
相似问题