1214. Мультифакториал

k-мультифакториалом числа n называется произведение всех положительных чисел вида n – k * x, x = 0, 1, 2, … и обозначается fac_k(n).

Приведем формальное определение мультифакториала:

fac_k(n) = n, если k ≥ n;

fac_k(n) = n * fack(n – k), если k < n;

По заданным n и k следует вычислить fac_k(n). Если результат будет строго больше 10¹⁸, то следует вывести “overflow”.

Вход. Два целых числа n и k (1 ≤ n, k ≤ 2 * 10⁹).

Выход. Значение fac_k(n). Если оно строго больше 10¹⁸, то вывести “overflow”.

Пример входа 1	Пример выхода 1
14 3	12320
Пример входа 2	Пример выхода 2
1000 2	overflow

РЕШЕНИЕ

математика

Анализ алгоритма

Для решения задачи достаточно непосредственно вычислить значение fac_k(n), используя его формальное определение.

Реализация алгоритма

Читаем входные данные. В переменной res будем накапливать результат. Переменная flag установится равной 1, как только значение res станет строго больше 10¹⁸.

scanf("%d %d",&n,&k);

res = 1;

flag = 0;

Запускаем цикл вычисления мультифакториала fac_k(n). Если в процессе вычислений просто сравнивать значение res с 10¹⁸, то при выполнении последнего умножения может возникнуть переполнение (переменная res имеет тип знакового 64 битового целого). Поэтому перед выполнением умножения следует проверить условие переполнения res * n > 10¹⁸, которое эквивалентно res > 10¹⁸ / n.

for(; n > 0; n -= k)

{

if (1e18 / n < res)

{

flag = 1;

break;

}

res *= n;

}

В зависимости от значения переменной flag выводим ответ.

if (flag) puts("overflow");

else printf("%lld\n",res);