조합 썸네일형 리스트형 [Fermat's little theorem] 페르마의 소정리 페르마의 소정리는 아래와 같이 정의 된다. (전제 조건) a와 m이 서로소여야 하며, m이 소수일 경우 am−1≡1 (mod m) 페르마의 소정리가 왜 필요할까? 보통은 modulus 연산의 나눗셈을 구하기 위한 응용으로 많이 사용된다. 다시 말하자면, 위의 수식을 아래와 같이 정리해 볼 수 있다는 말이다. am−2≡a−1 (mod m) modular 연산은 덧셈, 뺄셈, 곱셈에 대해서는 분배 법칙이 성립한다. (a+b) mod m=a mod m+b mod m (a−b) mod m=a mod m−b mod m $$ (a \times b) \ mod \ m.. 더보기 Next Permutation Permutation(순열)은 프로그래밍에서 흔하게 사용되는 개념이다. 나무 위키에는 다음과 같이 정의되어 있다. 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다. 위의 순열의 개념에서 "순서에 상관있게"를 "순서에 상관없게"로 바꾼 개념이 바로 조합(Combination)이다. n과 r이 일정한 수로 주어졌을 때, 어느쪽이 경우의 수가 더 많이 도출될까? 당연하게도, 순열이 그 경우의 수가 훨씬 많다. nPr=n×(n−1)×(n−2)×...(n−r+1)= n!(n−r)! nCr= nPrr! = 1r! $n!\over(n.. 더보기 이전 1 다음
