모듈러 산술 연산(feat. 백준 10430번 나머지)

백준 문제를 풀다가 모듈러 산술 연산의 분배법칙에 대해 알게되어 정리해보게 되었다.

문제
(A+B)%C는 ((A%C) + (B%C))%C 와 같을까?
(A×B)%C는 ((A%C) × (B%C))%C 와 같을까?

세 수 A, B, C가 주어졌을 때, 위의 네 가지 값을 구하는 프로그램을 작성하시오.

C++ 코드

#include <iostream>
using namespace std;
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    cout << (a+b)%c << "\n" << ((a%c) + (b%c))%c << "\n" << (a*b)%c << "\n" << ((a%c) * (b%c))%c;
}

당연히 풀이 자체는 그냥 간단한 산술 연산과 괄호만 잘 치면 된다.

문제에서 A+B나 A*B 수가 매우 큰 경우(오버플로우 발생할 수 있기 때문에)에 위와 같은 분배 법칙을 이용해서 수를 쪼개서 문제를 해결할 때 사용할 수 있다.

모듈러 연산 분배법칙의 간단한 증명