最小化一个区间内整数的除数

Question

我最近偶然发现了一个算法问题,我无法理解它.你得到一个正整数N <10 ^ 13,你需要选择一个非负整数M,这样得和:M N + N(N-1)/ 2的除数最小,介于1和N,包括在内.有人能指出我解决这个问题的正确方向吗？感谢您的时间.

Answer 1

找到大于N的素数P.有很多方法可以做到这一点.

如果N是奇数,那么M*N + N*(N-1)/2是N 的倍数.它必须可以被N的任何因子整除,但是如果我们选择M = P - (N-1)/2那么M*N + N*(N-1)/2 = P*N,那么它就不能被1和N之间的任何其他整数整除.

如果N是偶数,那么M*N + N*(N-1)/2是N/2的倍数.它必须可以被N/2的任何因子整除,但是如果我们选择M = (P - N + 1)/2(必须是整数),那么M*N + N*(N-1)/2 = (P - N + 1)*N/2 + (N-1)*N/2 = P*N/2它就不能被1和N之间的任何其他整数整除.