在一个区间内最小化一个整数的因数

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之间的任何其他整数整除。