문제 설명
정수 A, B, C에 대해 (A + B) % C, ((A % C) + (B % C)) % C, (A * B) % C, ((A % C) * (B % C)) % C의 값을 구하는 문제입니다.
입력
2 이상 10000 이하의 세 자연수 A, B, C에 대해
출력
W = (A + B) % C,X = ((A % C) + (B % C)) % C,Y = (A * B) % C,Z = ((A % C) * (B % C)) % C라 하면
풀이
문제에 주어진 연산을 구현하고사실 그대로 복붙해도 됩니다, 이를 각각 출력합니다.
C++
#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;
}
다른 풀이
사실 위의 두 식과 아래의 두 식은 같습니다. 이것은 증명을 통해 사실 확인이 가능합니다.
증명
먼저 합의 경우입니다.
$$
\text{Let} \begin{cases}A=nC+r\\B=mC+s\end{cases} ,
\text{then} \begin{cases}A\equiv r\pmod C\\B\equiv s\pmod C\end{cases}\\
(A+B)\begin{aligned}[t]
&=(nC+r)+(mC+s)\\
&=(n+m)C+(r+s)\\
&\equiv r+s\pmod C
\end{aligned}
$$
A+B와 A를 C로 나눈 나머지(r)와 B를 C로 나눈 나머지(s)의 합은 법 C에 대하여 합동임을 알 수 있고, 따라서 두 값을 C로 나눈 나머지는 서로 같음을 알 수 있습니다.
곱의 경우도 마찬가지로 증명할 수 있습니다. A×B와 두 수를 C로 나눈 나머지의 곱이 법 C에 대해 합동임을 보이면 두 값을 C로 나눈 나머지가 같음을 알 수 있습니다.
$$
(A\times B)\begin{aligned}[t]
&=(nC+r)(mC+s)\\
&=nmC^2 +(rm+ns)C+rs\\
&\equiv rs\pmod C
\end{aligned}
$$
따라서 아래의 두 식도 같은 값을 가집니다.
따라서 위의 두 식중 하나, 아래의 두 식중 하나만 골라서 두 번 출력해도 정답이 됩니다.
PS알못 OrbitHv의 PS