Задача
Николаю нужно доставить подарки для [latex]n[/latex] [latex](n ≤ 10^{18})[/latex] детей. Его интересует сколькими способами он может это сделать. Вам нужно дать ответ на этот простой вопрос. Так как это количество может быть очень большим, выведите результат по модулю [latex]m[/latex] [latex](m ≤ 2009)[/latex].
Входные данные
В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex].
Выходные данные
Вывести искомое количество способов.
Тесты
| Входные данные | Выходные данные |
| [latex]500[/latex] [latex]2001[/latex] | [latex]0[/latex] |
| [latex]4[/latex] [latex]5[/latex] | [latex]4[/latex] |
| [latex]4[/latex] [latex]7[/latex] | [latex]3[/latex] |
| [latex]15[/latex] [latex]213[/latex] | [latex]147[/latex] |
| [latex]10[/latex] [latex]3[/latex] | [latex]0[/latex] |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
/* package whatever; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Ideone { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n, m, k = 1; n = in.nextInt(); m = in.nextInt(); if ( n >= m) { System.out.print(0); } else { for ( int i = 2; i <= n; i++ ) { k = ( k * i ) % m; } System.out.print(k); } } } |
Решение задачи
Если [latex]m[/latex] является членом произведения [latex]n![/latex], то остаток от деления на [latex]m[/latex] равен [latex]0[/latex].В остальных случаях ищем [latex]n![/latex] с вычислением остатка от деления после каждого перемножения.
Ссылки
Условие задачи на e-olymp.com.
Код решения на ideone.com.