[알고리즘] [Professional] 조합

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	static long N,R;
	static long p = 1234567891;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			R = Integer.parseInt(st.nextToken());
			
			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 * div(b, p-2)) % p;
			
			System.out.println("#"+tc+" "+ans);
		}
	}
	private static long div(long b, long l) {
		if (l == 1) {
			return b;
		}
		
		long temp = div(b, l/2);
		if (l % 2 == 0) {
			return temp * temp % p;
		} else {
			return temp * temp % p * b % p;
		}
	}
	
}

 

 

나의 풀이

- 페르마의 소정리를 발상으로 사용해서 분할 정복으로 해결하는 문제