자연수 N과 정수 K가 주어졌을 때 이항 계수 (N,K)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static long factorial(int n){
long result=1L;
while(n>1){
result=result*n%1000000007;
n--;
}
return result;
}
public static long recursive(long base, int exponentiation){
if(exponentiation==1)
return base%1000000007;
long temp=base*base%1000000007;
if(exponentiation%2==1)
return base*recursive(temp, exponentiation/2)%1000000007;
else
return recursive(temp, exponentiation/2)%1000000007;
}
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s=br.readLine();
StringTokenizer st = new StringTokenizer(s);
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
long result=factorial(k)*factorial(n-k)%1000000007;
result=recursive(result, 1000000005);
result=factorial(n)*result%1000000007;
bw.write(result + "\n");
bw.flush();
}
}
이항 계수는 알고 있었지만 페르마의 소정리를 몰라서 어려웠다. mod 연산과 페르마의 소정리에 대해서 공부하고 난 뒤에 수학적으로 문제를 풀었다. 그것을 토대로 Recursive로 factorial을 구현하고 Math.pow 메소드를 사용해서 문제를 풀었다.
틀렸습니다(long의 범위를 한참 뛰어 넘어서 잘못된 연산. 하지만 수학적으로 틀린 줄 알고 긴 시간 동안 다시 페르마의 소정리를 공부하면서 삽질 했다, 반복문으로 factorial을 구현하고 pow 연산을 분할정복으로 구현하면서 계속 %연산을 해줬다)
😁