[백준/C언어] 10430번 - 나머지

백준 웹사이트 "10430번 - 나머지" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

10430번: 나머지

---

소스 코드

#include <stdio.h>

int main(void){
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);

    printf("%d\n", (A+B)%C);
    printf("%d\n", ((A%C)+(B%C))%C);
    printf("%d\n", (A*B)%C);
    printf("%d\n", ((A%C)*(B%C))%C);
    return 0;
}

---

문제 풀이

  \((A+B)\%C\) 는 \(((A\%C)+(B\%C))\%C\) 와 같은지, 또 \((A\times B)\%C\) 는 \(((A\%C)\times (B\%C))\%C\) 와 같은지 확인해보는 문제입니다. 간단한 문제이지만, 실제로 같은지 수식으로 한 번 확인해볼까요?

 

  우선, \(A\)와 \(B\)를 다음과 같이 정의합시다.

$$ A = a\cdot C+R_{A}, \;\;\; B=b\cdot C+R_{B} $$

\(a\) 와 \(R_{A}\)는 각각 \(A\)를 \(C\)로 나누었을 때의 몫과 나머지이며, \(b\) 와 \(R_{B}\)는 각각 \(B\)를 \(C\)로 나누었을 때의 몫과 나머지입니다. (자연스레 \( 0\leq R_{A},R_{B}<C\) 가 되겠지요)

$$ \begin{align} (A+B)\%C &= ((a\cdot C+R_{A})+(b\cdot C+R_{B}))\%C \\ &= ((a+b)\cdot C+R_{A}+R_{B})\%C \\ &= (R_{A}+R_{B})\%C \end{align} $$

이고,

$$ \begin{align} ((A\%C)+(B\%C))\%C &= ((a\cdot C+R_{A})\%C+(b\cdot C+R_{B})\%C)\%C \\ &= (R_{A}+R_{B})\%C \end{align} $$

이므로,

\((A+B)\%C\) 는 \(((A\%C)+(B\%C))\%C\) 와 같습니다.

 

마찬가지로,

$$ \begin{align} (A\times B)\%C &=((a\cdot C+R_{A})\times (b\cdot C+R_{B}))\%C \\ &=(a\cdot b\cdot C^{2}+(a\cdot R_{B}+b\cdot R_{A})\cdot C+R_{A}\cdot R_{B})\%C \\ &=(R_{A}\cdot R_{B})\%C \end{align} $$

이고,

$$ \begin{align} (((A\%C)\times (B\%C))\%C &= ((a\cdot C+R_{A})\%C\times (b\cdot C+R_{B})\%C)\%C \\ &= (R_{A}\cdot R_{B})\%C \end{align} $$

이므로,

\((A\times B)\%C\) 는 \(((A\%C)\times(B\%C))\%C\) 와 같습니다.