7441. Факториал

Вход. Одно целое число n (1 ≤ n ≤ 10¹⁸).

Выход. Вывести n! (mod 3469708049238200000).

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

РЕШЕНИЕ

математика

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

Заметим, что 3469708049238200000 = 2⁶ * 5⁵ * 7⁹ * 11³ * 17 * 19. Как только в разложении числа n! будут присутствовать множители из множества {2⁶, 5⁵, 7⁹, 11³, 17, 19}, то n! (mod 3469708049238200000) = 0. Наименьшим числом, которое удовлетворяет этому условию, будет n = 56. Число 55! делится на 7⁸, но не делится на 7⁹. Таким образом ответ равен 0 при n ≥ 56.

Для языка С / С++ типа unsigned long long недостаточно для избежания переполнения. Используйте язык Java или Python.

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

import java.util.*;

import java.math.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long n = con.nextLong();

BigInteger res = BigInteger.ONE;

BigInteger MOD = new BigInteger("3469708049238200000");

for (int i = 1; i <= n; i++)

{

res = res.multiply(BigInteger.valueOf(i)).mod(MOD);

if (res == BigInteger.ZERO) break;

}

System.out.println(res);

con.close();

}

}