[BOJ] 백준 이항 계수 3 11401

[BOJ] 백준 이항 계수 3 11401

---

페르마의 소정리

• p가 소수이면, 모든 정수 a에 대해 a^p ≅ a (mod p)
• p가 소수이고 a가 p의 배수가 아니면 a^p-1 ≅ 1 (mod p)

---

응용

• 정수 a, b, p에 대해 (p는 소수) 이하의 식으로 정리할 수 있다.
• b^p-1 = b*b^p-2 ≅ 1 (mod p)
• b^p-2 ≅ b^-1 (mod p)
• a\ * b^-1 % p ≅ a\ * b^p-2 % p (mod % p)

---

풀이

• p는 1,000,000,007로 주어졌다.
• _nC_k 는 a / b = a * b^-1로 표현할 수 있다. (a = n! / (n - k)!, b = k!)
• a * b^-1 % p = a * b^p-2 / b^p-1 % p≅ a * b^p-2 % p (mod p)
• a % p와 b^p-2 % p를 따로 구해준 뒤 곱한 결과에 % p를 취한다.