728x90 반응형 이항 계수 31 [백준] 11401번 : 이항 계수 3 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/11401 1. 문제 설명2. 풀이과정해당 문제는 이항 계수를 구하는 식 N! / (N - K)! * K! 을 1,000,000,007로 나눈 나머지를 구하는 문제이다.문제를 해결하기 위해서는 나머지 연산의 분배 법칙과 페르마의 소정리를 활용한다.분배 법칙은 (A x B) % p = ((A % p) X (B % p)) % p이다.페르마의 소정리는 p가 소수일 때 a^p = a % p를 의미하며, 양 변을 a^2로 나눠주면 a^(p - 2) = 1/a % p 가 된다.이를 활용하기 위해 N! / (N - K)! * K! 식을 곱셈으로 정리하면, N! * (N - K)! ^ -1 * K! ^ -1로 변환할 수 있고 이를 1,000,000,007로 나눈.. 2024. 7. 10. 이전 1 다음 728x90 반응형
