처음 문제를 해결할 때 아무생각없이 주어진 대로
(A+B)%C, ((A%C)+(B%C))%C, (A*B)%C, ((A%C)*(B%C))%C를 계산하여 해결하였다.
추후 알고리즘 문제를 더 풀면서 나머지 연산의 분배법칙에 관련된 문제라는 것을 알게되었다.
(A+B)%C = ((A%C)+(B%C))%C
나머지 연산은 다음과 같이분배법칙이 성립하는데
A = a * C + r1
B = b * C + r2
A는 C로 나누었을 때 몫a와 나머지r1으로 나타낼 수 있고
B도 마찬가지로 몫b와 나머지r2로 나타낼 수 있다.
(A+B)%C에 치환하면
(a*C + r1 + b*C + r2)%C가 되고
a*C와 b*C는 A를 C로 나누엇을 대 몫임으로 %C연산을 하면 0이된다.
따라서 (A+B)%C = (r1 + r2)%C이고
r1는 A/C의 나머지임으로 r1 = A%C
r2도 마찬가지로 r2 = B%C가 됨으로
(A+B)%C = ((A%C)+(B%C))%C가 성립하는 것을 알 수 있다.
더하기뿐만 아니라 빼기, 곱셈도 성립된다.
단, 나누기는 성립하지 않는다.