Матч 335, Мультифакториал (Multifactorial)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

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

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

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

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

Класс: Multifactorial

Метод: string calcMultiFact(int n, int k)

Ограничения: 1 £ n, k £ 2 * 10⁹.

Вход. Два целых числа n и k.

Выход. Строка, содержащая значение fac_k(n). Если оно больше 10¹⁸, то вывести “overflow”.

Пример входа

n	k
14	3
5	4
1000	2

Пример выхода

“12320”

“5”

“overflow”

РЕШЕНИЕ

элементарные вычисления

Вычисляем требуемое значение мультифакториала в цикле и следим за переполнением. Произведение res * n на очередном шаге даст переполнение тогда и только тогда, когда 1e18 / n < res. Преобразовываем результат res в строку и возвращаем как результат функции.

ПРОГРАММА

#include <cstdio>

#include <string>

using namespace std;

class Multifactorial

{

public:

string calcMultiFact(int n, int k)

{

long long res = 1;

char s[50];

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

{

if (1e18 / n < res) return "overflow";

res *= n;

}

sprintf(s,"%lld",res);

return (string)s;

}

};