Задача 374
Максимальное произведение разбиения

Разбиение целого числа n — это представление n в виде суммы натуральных чисел — частей.

Разбиения, которые отличаются только порядком слагаемых, считаются одинаковыми. Разбиение n на различные части — это разбиение n, в которое каждая часть входит не более одного раза.

Разбиения на различные части числа 5:
5, 4+1 и 3+2.

Пусть f(n) — максимальное произведение частей среди таких разбиений n на различные части, и пусть m(n) — количество элементов разбиения n с этим произведением.

Тогда f(5)=6 и m(5)=2.

Для n=10 разбиением с наибольшим произведением является 10=2+3+5, которое дает f(10)=30 и m(10)=3.
И их произведение, f(10)·m(10) = 30·3 = 90.

Можно убедиться, что
f(n)·m(n) для 1 ≤ n ≤ 100 = 1683550844462.

Найдите f(n)·m(n) для 1 ≤ n ≤ 1014.
Дайте ответ по модулю 982451653 (это 50-миллионное простое число).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net