Минимизируйте количество делителей целого числа в интервале

Question

Недавно я наткнулся на алгоритмическую проблему, и я не могу ее решить. Вам дано положительное целое число N < 10^13, и вам нужно выбрать неотрицательное целое число M так, чтобы сумма: M N + N(N-1) / 2 имела наименьшее число делителей, лежащих между 1 и N включительно. Может кто-нибудь указать мне правильное направление для решения этой проблемы? Спасибо за ваше время.

Answer 1

Найдите простое число P больше N. Есть несколько способов сделать это.

Если 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.