1010 - 다리 놓기

동쪽에 다리가 N개 있고, 서쪽에 다리가 M개 있을 때
답은 _NC_M (조합론:Combination) 과 같다.

주의해야 할 점이라면, 팩토리얼 / 팩토리얼 연산은 오버플로우를 조심해야한다.
30!만 되어도 수가 엄청 커져서 나중에 100! 정도는 long long이라도 저장 못한다.

그럼 어떻게 해야할까?

조합(combination)은 _nC_r 에서 분자가 n! 이고 분모는 (n-r)! * r! 이다. 여기서 n > r 을 만족한다면 분자는 항상 분모의 소인수를 가진다. (수학적으로 증명하기엔 포스팅이 길어지므로 생략)

즉, 분자의 각 소인수들은 분모의 소인수들 중에 하나로 나눌 수 있다(!)
근데 _nC_r 의 결과가 자연수로 나누어 떨어지는 건 아무도 의심하지 못한다.

분자와 분모를 소인수 분해하여 개별적으로 약분하고 연산한다면 오버플로우를 방지할 수 있다.