모듈러 연산

문제를 풀다보면 특정 값으로 나눈 나머지값을 구하라는 문구를 많이 접하게 되었다.

자료형 범위를 넘어가지 않도록 조건을 제시해 준 것인데, 

만약 전체 곱의 나머지를 구하라고 하면, 전체 곱이 나오기 전에 오버플로우가 발생할 수 있다.

이때 사용하는 것이 모듈러 연산이다.

 

모듈러 연산 (Modular Arithmetic)

어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산

 

모듈러 합동 (Modular Congruent)

두 A,B 숫자가 M을 모듈러한 결과 값이 같다면 모듈러 합동관계라고 한다.

• A mod M = b mod N
• A ≡ B mod M 

 

모듈러 합동식

• A  = B + K * M (K는 정수)

이 식에서 B를 이항하게 되면,

• A - B = K * M

두 정수 A, B와 양의 정수 M에 대해 다음이 성립하면 모듈러 합동관계이다.

예를 들어 A = 10 , B = 4 이고 mod 3에 대해 합동관계라면, 10 - 4 = 2 * 3 으로 표현할 수 있다.

 

모듈러 합동 동치

다음 식은 모듈러 합동의 동치이다. ( ≡ 표시)

• A ≡ B (mod C)
• A mod C = B mod C
• A = B + K * C ↔ A - B = K * C

 

모듈러 연산 

• 덧셈 ( A + B ) % M = ( ( A % M ) + ( B % M ) ) % M
• 뺄셈 ( A - B ) % M = ( ( A % M ) - ( B % M ) ) % M
• 곱셈 ( A * B ) % M = ( ( A % M ) * ( B % M ) ) % M

 

 

 

더 자세하고 이해하기 좋은 설명은 아래 링크를 통해 확인하면 된다!

 

[참조]

https://developer-mac.tistory.com/84

https://gamedevlog.tistory.com/44