[백준/Python] 10430 - 나머지

 

10430번: 나머지

문제

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

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

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

입력

첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)

출력

첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다.

예제 입력 1

5 8 4

예제 출력 1

1
1
0
0

풀이

input = __import__('sys').stdin.readline
a, b, c = map(int, input().split())
print((a + b) % c)
print(((a % c) + (b % c)) % c)
print((a * b) % c)
print(((a % c) * (b % c)) % c)

문제에서 요구하는 사칙연산들을 출력하면 되는 간단한 문제입니다.

---

사실 이 문제에서 관심을 가질만한 부분은 바로 출력해야 하는 연산들입니다.

어떤 두 수의 합(또는 곱)의 나눗셈의 나머지와 이 나머지들의 합(또는 곱)의 똑같은 수로 나누었을 때의 나머지가 같다는 점이 굉장히 흥미로운데요, 이번 풀이에서는 이를 증명하는 부분을 중점적으로 다뤄보도록 하겠습니다.

어떤 수 \(x\)를 임의의 수 \(C\)으로 나눴을 때의 몫을 \(Q_x\), 나머지를 \(R_x\)라고 합시다.

덧셈의 경우를 예로 들어볼까요?

어떤 임의의 수 A, B에 대해 (A + B) % C == ( (A % C) + (B % C) ) % C가 성립함을 보여야 합니다.

(이 때, C는 전부 동일하다.)

이 때 A%C와 B%C는 각각 \(R_A\),  \(R_B\)이고

(A + B) % C == ( \(R_A\) + \(R_B\) ) % C

\(A = (Q_A  \times C) + R_A\)

\(B = (Q_B  \times C) + R_B\)

\(A + B = (Q_A + Q_B)C + (R_A + R_B)\)

즉 (A + B) % C는

\(((Q_A + Q_B)C + (R_A + R_B))\) % C

이제 \(((Q_A + Q_B)C + (R_A + R_B))\) % C == ( \(R_A\) + \(R_B\) ) % C 임을 증명합시다.

i) \(R_A + R_B < C\)

\(((Q_A + Q_B)C + (R_A + R_B))\) % C == ( \(R_A\) + \(R_B\) ) % C
\(R_A + R_B\) == ( \(R_A\) + \(R_B\) ) % C
\(R_A + R_B < C\) 이므로 우변의 계산에서 몫은 0, 나머지는 피제수 그대로 \(R_A + R_B\)입니다.
등식이 참으므로 성립합니다.

ii) \(R_A + R_B \geq C\)

\(R_A + R_B = kC + r\) 이라고 합시다. (\(k\)는 임의의 자연수,  \(r\)은 임의의 음이 아닌 정수)
\(((Q_A + Q_B)C + (R_A + R_B))\) % C == ( \(R_A\) + \(R_B\) ) % C
\(((Q_A + Q_B)C + (kC + r))\) % C == ( \(kC + r\) ) % C
\(((Q_A + Q_B + k)C + r)\) % C == ( \(kC + r\) ) % C
양변 모두 C로 나누었을 때 나머지가 \(r\)이 되므로 성립합니다.

 

뺄셈과 곱셈 또한 비슷한 과정으로 증명할 수 있습니다!

나눗셈의 경우도 이와 같이 증명할 수 있으나 수식이 조금 복잡해 질 것 같네요 :)