在一個區間內最小化一個整數的因數

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