我最近偶然发现了一个算法问题，但我无法解决它。给定一个正整数 N < 10^13，并且您需要选择一个非负整数 M，这样总和：M N + N (N-1) / 2 具有介于 1 和N，包括在内。有人可以指出我解决这个问题的正确方向吗？感谢您的时间。
问问题
82 次
1 回答
5
找到一个大于 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 之间的任何其他整数整除。
于 2016-04-08T18:15:07.107 回答