정수론2 Euler phi function 오일러 피 함수 Euler phi function 오일러 피 함수 $\varphi \left ( n \right )$ = $n$ 이하 자연수 중 $n$ 과 서로소인 수의 개수 소수 $p$와 자연수 $a$에 대하여 다음을 만족한다. $\varphi \left ( p \right )=p-1$ $\varphi \left ( p^a \right )=p^a-p^{a-1}={p^a} \left ( 1-\frac{1}{p} \right ) $ 또한 $\left ( m,n \right )=1$ 인 두 자연수 $m$, $n$에 대하여 $\varphi \left ( mn \right )=\varphi \left ( m \right ) \varphi \left ( n \right ) $ 따라서 소수 $p$, $q$와 자연수 $a$, $b$.. 2021. 4. 16. BOJ13977 이항 계수와 쿼리 www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net = 16134 조합(Combination) 15791 세진이의 미팅 페르마의 소정리에 의해 p가 소수이고 a가 정수일 때, a^p≡a (mod p) ⇒ a^(p-1)≡1 (mod p) ⇒ a^(p-2)*a≡1 (mod p) 즉 mod p에서 a의 역원이 a^(p-2)가 된다. a^p구하는 건 재귀함수로 해주고 long long 주의 13977번의 경우 N!, K!, (N-K)!을 모두 구해야하니까 while 돌리기 .. 2021. 1. 12. 이전 1 다음
