[SWEA-Professional] 조합 (페르마소정리)

이 문제도 싸피에서 CT시간에 다뤘던 문제이다.

문제만 보면 참 쉬워보이는데, 페르마의 소정리를 이용하라고 하셨다.

 

페르마의 소정리란 p가 소수이고, a가 p로 나누어지지 않는 정수 일 때 성립하는 법칙인데,

간단하게 이 두 개의 식으로 설명할 수 있다. 

소수 어떤 수의 p승을 소수 p로 나머지 연산을 하면 어떤 수가 나온다는 것이다.

 

예를 들어서 3으로 생각해보면,

3^1 = 3 (mod 5) 

3^2 = 4 (mod 5)

3^3 = 7 (mod 5)

3^4 = 1 (mod 5)

3^5 = 3 (mod 5)

 

이 패턴이 반복된다. 

어떤 수의 제곱수에 소수 p를 이용해 나머지 연산을 취한 값은 소수 p-1개의 패턴으로 반복된다는 정리이다. 

 

사실 처음에는 도대체 이 정리를 이용해서 이 문제를 어떻게 풀으라는건가... 싶었다.

하지만 잘 생각해보면, 우리는 nCr을 구해야 한다.

nCr 을 수식으로 바꿔보면

nCr = n! / r!(n-r)! 인데, 나누기 연산을 사용하기 위해 분수가 아닌 곱셈의 형태로 바꿔주어야 한다.

아까 페르마 소정리에서 

a^(p-1) = 1(mod p) 였고, 여기서 양 부분을 a로 나눠주면 a^(p-2) = a-1 (mod p)라는 값을 얻을 수 있다.

따라서, r!(n-r)! 이 부분을 a로 치환하면,  n! * a^(p-2) (mod p) 라는 식을 얻을 수 있다.

 

div라는 함수에 밑수 부분인 a와 지수 부분인 b를 넣어준다.

b가 1이라면 a를 return 해주고,

b가 2로 나누어 떨어진다면 (a^b)^2 인 것이니, 이 것을 p로 나머지 연산을 해준 것,

b가 2로 나누어 떨어지지 않는다면  (a^b)^2 *a를 mod p 해준 것을 return 해준다.

 

또 다른 점은, 보통의 조합 연산에서는 n! / r!(n-r)! 이 식을 쓰지만 나는 미리 약분해준 값을 넣어주었다.

약분을 하면 n 부터 r개 까지의 곱 / r! 이 되기 때문에 이 값을 넣어주었다. 

 

package ex_0419;

import java.util.Scanner;

public class 조합 {
	static long N,R;
	static long p = 1234567891;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			N = sc.nextInt();
			R = sc.nextInt();
			
			long a = 1;
			long b = 1;
			
			long t = Math.min(R, N-R);
			
			for(int i=0; i<t; i++) {
				a = a*(N-i)%p;
				b = b*(t-i)%p;
			}			
			long ans = (a%p*div(b,p-2)%p)%p;
			
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static long div(long a, long b) {
		if(b==1)
			return a;
		long tmp = div(a, b/2);
		if(b%2 == 1)
			return tmp*tmp%p*a%p;
		else
			return tmp*tmp%p;
	}
}