[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
- 뺄셈 결과 가 음수 인 경우 방지
일반적으로 나눗셈에 대해서는 분배법칙을 적용 할 수 없다.
다만, 특수한 경우에 대해서는 페르마의 소정리를 이용하여 구할 수 있다.
페르마의 소정리 란?
'알고리즘 > 기타' 카테고리의 다른 글
| 페르마의 소정리 (0) | 2024.09.03 |
|---|---|
| farthest insertion (0) | 2024.08.15 |
| 이분 탐색, 하한 / 상한 값 탐색 (1) | 2023.05.13 |
| Lazy propagation (0) | 2023.03.10 |
| 플로이드의 모든 쌍 최단거리 알고리즘 (0) | 2022.11.30 |