[백준/BOJ] 10430번 나머지 (C++)

10430번: 나머지

문제의 소재

세 정수 A, B, C를 입력받아 (A+B)%C, ((A%C)+(B%C))%C, (A×B)%C, ((A%C)×(B%C))%C를 한줄씩 출력하는 문제이다.

해답

해답은 간단하다. 다만 각각의 두 수가 실제로 같은지 수학적으로 확인해보자.

 

$$A=p1 \times C+r1$$$$B=p2 \times C+r2$$라 하면 제수(divisor) $p1$, $p2$와 나머지(remainder) $r1$, $r2$는 $$0 \leq p1, p2$$$$0 \leq r1, r2 < C$$를 만족한다.

 

$$(A+B)\%C$$에 $A$, $B$를 대입하면 몫과 제수의 곱 부분은 $C$로 나누면 나머지가 $0$이므로 $$(A+B)\%C=(r1+r2)\%C$$이다.

$$((A\%C)+(B\%C))\%C$$에 $A$, $B$를 대입하면 $$A\%C=r1$$$$A\%C=r2$$이므로 $$((A\%C)+(B\%C))\%C=(r1+r2)\%C$$이다.

따라서 두 값 $(A+B)\%C$와 $((A\%C)+(B\%C))\%C$는 같다.

 

마찬가지로 $$(A \times B)\%C$$에 $A$, $B$를 대입하면 $$A \times B=p1 \times p2 \times C ^{2}+(p1 \times r2 + p2 \times r1) \times C+r1 \times r2$$이다. $C$가 곱해진 항은 $C$로 나누면 나머지가 $0$이므로 $$(A \times B)\%C=(r1 \times r2)\%C$$이다.

$$((A\%C) \times (B\%C))\%C$$에 $A$,$B$를 대입하면 $$A\%C=r1$$$$B\%C=r2$$이므로 $$((A\%C) \times (B\%C))\%C=(r1 \times r2)\%C$$이다.

따라서 두 값 $(A \times B)\%C$와 $((A\%C) \times (B\%C))\%C$는 같다.

 

// BOJ_10430.cpp
#include <iostream>
using namespace std;

int main()
{
    int A, B, C;
    
    cin>>A>>B>>C;
    cout<<(A+B)%C<<endl;
    cout<<((A%C)+(B%C))%C<<endl;
    cout<<(A*B)%C<<endl;
    cout<<((A%C)*(B%C))%C<<endl;
    
    return 0;
}