백준 11401번 : 이항계수 [C#]

이항계수란 무엇인가이렇다고 합니다. 개념은 한 번 읽어보고, 공식을 보면 팩토리얼을 사용하네요. N이 400만인데, 400만의 팩토리얼을 구한다는건 숫자가 너무 커지고, 중간에 어떤 연산을 거쳐서 숫자의 크기를 어느정도 유지해가며 N!을 구해야겠습니다. 1000000007으로 나누는 과정에서의 나머지는 나머지 연산 분배법칙을 활용할 수 있을 것 같습니다. (mod m) = m으로 나눈 나머지라는 뜻. 추가로 페르마의 소정리까지 알아야 이 문제를 해결할 수 있습니다. a가 정수, p가 소수일 때 이 공식이 성립하는데, 여기서 a= N이든 R이 될 수 있고, P는 1000000007입니다. a와 1이 서로소이기 때문에 양 변을 a로 나누면 위에서 배운 내용을 어떻게 적용하냐면 1. 이 공식으로 분모..

2026.03.14