Задача

Николаю нужно доставить подарки для $n$ $(n ≤ 10^{18})$ детей. Его интересует сколькими способами он может это сделать. Вам нужно дать ответ на этот простой вопрос. Так как это количество может быть очень большим, выведите результат по модулю $m$ $(m ≤ 2009)$ .

Входные данные

В одной строке заданы два натуральных числа $n$ и $m$ .

Выходные данные

Вывести искомое количество способов.

Тесты

Входные данные	Выходные данные
$500$ $2001$	$0$
$4$ $5$	$4$
$4$ $7$	$3$
$15$ $213$	$147$
$10$ $3$	$0$

Код программы

/* 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); 
    	}
	}
}

/* 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);

}

Решение задачи

Если $m$ является членом произведения $n!$ , то остаток от деления на $m$ равен $0$ .В остальных случаях ищем $n!$ с вычислением остатка от деления после каждого перемножения.

Ссылки

Условие задачи на e-olymp.com.

Код решения на ideone.com.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: кол-во способов

e-olymp 513. Проблема Николая