나머지 연산의 특징 : 백준 1629번 백준 13171번

나머지 연산의 특징

나머지 연산은 기본적으로 결합, 분배, 교환법칙이 모두 성립하지 않는다. 그래서 사용할 때 계산순서와 위치를 주의해야 한다. 단, 나머지 연산에서 성립하는 독특한 법칙도 있다.

 

a를 b로 나눈 나머지 a mod b = a % b 라고 표현하기로 하자. 이 때 나머지는 다음과 같은 식들이 항상 성립한다.

 

( a + m ) % m = a % m

( a + b ) % m = ( ( a % m ) + ( b % m ) ) % m

 

증명) 

0 보다 큰 어떤 정수 x1, a1, B, c1, x2, a2, c2가 있다고 하자.

여기서 c1, c2는 B보다 작은 자연수이다.

 

x1 = a1 * B + c1

x2 = a2 * B + c2 이라고 하자.

 

(x1 + x2)

 = (a1 * B + c1) + (a2 * B + c2)

= (a1 * B + a2 * B) + (c1 + c2)

= (a1 + a2) * B + (c1 + c2)

 

따라서

(x1 + x2) % B = (c1 + c2) % B 이다.  (가)

 

 

(x1 % B + x2 % B)

= (a1 * B + c1) % B + (a2 * B + c2) % B

= (c1 + c2)

 

따라서

(x1 % B + x2 % B) % B = (c1 + c2) % B 이다. (나)

 

 

(가)와 (나)를 종합하면

(x1 + x2) % B = (x1 % B + x2 % B) % B

 

( a * b ) % m = ( ( a % m ) * ( b % m ) ) % m

증명) 

(x1 * x2)

 = (a1 * B + c1) * (a2 * B + c2)

= (a1 * B * a2 * B) + (a1 * B * c2) + (c1 * a2 * B) + (c1 * c2)

= ((a1 * B * a2 + (a1 * c2) + (c1 * a2)) * B + (c1 * c2)

 

따라서

(x1 * x2) % B = (c1 * c2) % B 이다.  (가)

 

 

(x1 % B * x2 % B)

= (a1 * B + c1) % B * (a2 * B + c2) % B

= (c1 * c2)

 

따라서

(x1 % B * x2 % B) % B = (c1 * c2) % B 이다. (나)

 

 

(가)와 (나)를 종합하면

(x1 * x2) % B = (x1 % B * x2 % B) % B

 

 

백준 1629번 문제

jeon9825/TIP

백준 13171번 문제

jeon9825/TIP