помогите решить задачу за короткое алгоритмическое время
1.5.4. Факториал по модулю
Ограничение времени 1 секунда
Ограничение памяти 64Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Во входном файле задано целое положительное число N, не превосходящее 10⁹. Найдите остаток от деления числа (произведения всех чисел от 1 до N) на 10⁶+3.
Формат ввода
Первая строка входного файла содержит одно целое число N (1 ≤ N ≤ 10⁹).
Формат вывода Выведите одно целое число — ответ к задаче.
Пример 1:
Ввод - 3 ; Вывод - 6
Пример 2:
Ввод - 10 ; Вывод - 628791
Ответы (1 шт):
Автор решения: Harry
→ Ссылка
- Очевидно, что при N >= 1000003 значение N! делится на 1000003.
- Очевидно, что при N < 1000003 значение N! на 1000003 нацело не делится, т.к. 1000003 — число простое.
- Очевидно, что если число А с остатком от деления на Р, равным а, умножить на В, то остаток от произведения равен остатку от произведения а*В от деления на Р.
- Очевидно, что произведение двух чисел порядка 1000000 в 4-байтный тип
intне влезет, и надо использоватьlong long.
А из этих очевидностей очевидным образом получается... ну, у меня с красивым форматированием :) — 8 строк кода, которые не привожу, чтобы не лишать вас удовольствия написать их самостоятельно...