algorithm - 最小化区间内整数的约数

Question

我最近偶然发现了一个算法问题，我无法解决它。给定一个正整数 N < 10^13，你需要选择一个非负整数 M，使得和:MN + 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 之间的其他整数。