[algo] 나머지 분배 법칙

정답을 15746으로 나눈 나머지를 출력하시오

같은 문제들이 있다.

ex. 백준 1629번 곱셈
https://www.acmicpc.net/problem/1629

매우 큰 값을 대비한 것인데, 이때 출력 직전에만 나머지 연산을 진행하면 오버플로가 발생할 확률이 높다.
오버플로를 방지하려면 분배법칙을 이용하여 미리미리 나머지 연산을 진행하는 것이 좋다.

나머지 분배 법칙

덧셈

(x + y) % m == ((x % m) + (y % m)) % m

var x = 1596372
var y = 392949112
var m = 15746
print((x + y) % m) // 13708
print((x % m) + (y % m)) // 13708

곱셈

(x *y) % m == ((x % m) * (y % m)) % m

var x: Int8 = 55
var y: Int8 = 82
var m: Int8 = 25
// print((x * y) % m) // runtime error
print((55 * 82) % Int(m)) // 10
print(((x % m) * (y % m)) % m) // 10

뺄셈

(x - y) % m == ((x % m) - (y % m) + m) % m

뺄셈의 경우 나머지가 음수가 나오는 것을 방지하기 위해 마지막에 m을 더한 후 나머지를 연산한다.

var x = 1596372
var y = 392949
var m = 15746
print((x - y) % m) // 6727
print(((x % m) - (y % m) + m) % m) // 6727

x-y가 음수인 경우 다른 결과를 얻는다.

var x = 1596372
var y = 39294911
var m = 15746
print((x - y) % m) // -2615
print(((x % m) - (y % m) + m) % m) // 13131

나눗셈

나눗셈에는 나머지 분배법칙이 적용되지 않는다.

출처

https://youseokhwan.me/blog/remainder-distribution-property/