전체 글 (679) 썸네일형 리스트형 페르마의 소정리 [1. 정의]p 가 소수이고, (prime number) , a 가 정수일 때# ap ≡ a (mod p)# ap 를 p 로 모듈러 연산을 할 경우, 그 나머지는 a 이다.특히, p 가 소수이고, a 가 p 의 배수가 아닐 때 (a 와 p 가 서로소 일 때)# a(p-1) ≡ 1 (mod p)# a(p-1) 을 p 로 모듈러 연산 한 경우, 그 나머지는 항상 1 이다.[2. 활용]2번 정의에서, 양변(?) 에 a-1 을 곱하면, 아래와 같은 식이 성립한다.모듈러 연산 역원(?) a(p-2) ≡ a-1 (mod p)즉, a-1 mod p = a(p-2) mod p 이다. 모듈러 연산 [1. 개요]모듈러 연산의 여러가지 특징을 정리한다.[2. 표기]일반적인 표기A mod B == A % B합동 관계A mod N == B mod N 일 때 아래와 같이 표기A ≡ B (mod N)[3. 분배 법칙]덧셈(A + B) mod C = ((A mod C) + (B mod C)) mod C곱셈(A * B) mod C = ((A mod C) * (B mod C)) mod C두 수의 곱이 overflow 날 수 있을 지도,뺄셈(A - B) mod C = ((A mod C) - (B mod C) + C) mod C뺄셈 결과 가 음수 인 경우 방지일반적으로 나눗셈에 대해서는 분배법칙을 적용 할 수 없다.다만, 특수한 경우에 대해서는 페르마의 소정리를 이용하여 구할 수 있다. 페르마의 소정리 란?https.. set vs multiset [1. 개요] [2. 예제]#include #include int main(){ std::set s; std::multiset ms; for (int i=1; i 출력1 1 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 1 2 3 4 5 6 7 8 9 10 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 => 이전 1 2 3 4 5 6 ··· 227 다음