[SWEA] 5607 : 조합 (풀이중)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWXGKdbqczEDFAUo&categoryId=AWXGKdbqczEDFAUo&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=2 

SW Expert Academy

처음에 쉬운 문제라고 생각하고 풀었는데 계속 틀리길래 뭐지? 하고 보니, N의 크기가 너무 커서 페르마의 소정리를 사용해야 한다고 했다.페르마의 소정리를 공부할 수 있는 계기가 됨.

 

풀이과정

조합은 nCr = n! / (r! * (n - r)!) 이다.

>> 이 식을 n! * (1 / (r! * (n - r)!))로 바꾸면 n! * (r! * (n - r)!)^-1이 된다.

 

여기서 페르마의 소정리의 a^(p - 1) ≡ 1 (mod p)를 생각해보자.

>> 각각 a^-1을 곱해주면 a^(p-2) ≡ a^-1 (mod p)가 된다.

>> 이 때의 a는 r! * (n - r)!이다.

 

최종적으로  n! * a^-1 ≡ n! * a^( p -2) (mod p)이다.

 

따라서 n! * a^(p - 2) % p 를 구해주면 된다.

 

p-2의 값이 상당히 크므로 분할정복방식을 사용해야 한다.