我们给出一个整数'N'。我们可以在范围(1到z)中选择任意2个数字(a和b)。L的值由下式给出,
L = Max(( (N%a) %b) %N)
我们必须计算给出(L)值的对的数量(a,b)。我知道一个简单粗暴的办法,一,O(n ^ 2)解决方案。有没有更有效的方法来解决这个问题?!谢谢
发布于 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
。
https://stackoverflow.com/questions/-100008951
复制相似问题