SWEA_5607 조합(자바) / 페르마의 소정리

문제 링크

SW Expert Academy

문제는 간단합니다..

 

N과 R이 주어지고 , 조합의 갯수 nCr을 구하는 문제입니다.

 

하지만, 이 문제는 페르마의 소정리에 대해서 알아야 문제를 풀 수 있습니다.

 

package com.Expert;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Expert_5607 {
	static int MOD = 1234567891;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			String[] line = br.readLine().split(" ");
			int n = Integer.parseInt(line[0]);// 10
			int r = Integer.parseInt(line[1]);// 2
			
			//FACTORIAL 미리 구해 놓기 N!
			long[] facto = new long[n + 1];//1! ~ 10!
			facto[1] = 1; //1! = 1			
			for (int i = 2; i <= n; i++) {
				facto[i] = (facto[i - 1] * i) % MOD;
			}
			
			long bottom = (facto[r] * facto[n-r]) % MOD;// 1/a에서 a에 해당하는 값
			bottom = pow(bottom, MOD -2);			
			
			System.out.println("#" + tc + " " + (facto[n] * bottom) % MOD );
		}
	}

	//
	private static long pow(long a, int b) {//a의 b승
		if(b == 0)
			return 1;
		
		else if(b == 1)
			return a;
		
		if(b % 2 == 0) {//b가 짝수인 경우
			long tmp = pow(a, b/2);
			return (tmp * tmp) % MOD;
		}
		
		long tmp = pow(a, b-1) % MOD;//pow(2,5) ==> pow(2,4)
		return (tmp * a) % MOD;
	}
}

위키피디아 링크

페르마의 소정리 - 위키백과, 우리 모두의 백과사전

 

이 부분을 활용하는 문제입니다... 이 정리를 모르면 풀기 까다로운 문제인거 같습니다.

 

nCr = n! / r! (n-r)! 의 공식을 활용할 수 있습니다.

 

이때 분모의 경우 r! (n-r)!  이것을 해결하기 위해서 사용이 됩니다.

 

r! (n-r)! ^-1 입니다 이는 페르마 소정리에 의해서

 

r!(n-r)!^(123456789-2) 와 동일합니다. 

 

package com.Expert;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Expert_5607 {
	static int MOD = 1234567891;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			String[] line = br.readLine().split(" ");
			int n = Integer.parseInt(line[0]);// 10
			int r = Integer.parseInt(line[1]);// 2
			
			//FACTORIAL 미리 구해 놓기 N!
			long[] facto = new long[n + 1];//1! ~ 10!
			facto[1] = 1; //1! = 1			
			for (int i = 2; i <= n; i++) {
				facto[i] = (facto[i - 1] * i) % MOD;
			}
			
			long bottom = (facto[r] * facto[n-r]) % MOD;// 1/a에서 a에 해당하는 값
			bottom = pow(bottom, MOD -2);			
			
			System.out.println("#" + tc + " " + (facto[n] * bottom) % MOD );
		}
	}

	//
	private static long pow(long a, int b) {//a의 b승
		if(b == 0)
			return 1;
		
		else if(b == 1)
			return a;
		
		if(b % 2 == 0) {//b가 짝수인 경우
			long tmp = pow(a, b/2);
			return (tmp * tmp) % MOD;
		}
		
		long tmp = pow(a, b-1) % MOD;//pow(2,5) ==> pow(2,4)
		return (tmp * a) % MOD;
	}
}