[10430번] 나머지

https://www.acmicpc.net/problem/10430

10430번: 나머지

 

 

종종 문제에서 구하는 정답의 크기가 너무 클 경우 정수로 저장할 수 있는 범위에 한계가 있기 때문에 결과를 X로 나눈 나머지를 구하라고 하기도 합니다.

이 문제에서는 단순히 두 식의 결과값이 동일한지를 값을 출력만 하면 됩니다.

 

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

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

 

질문의 정답은 둘다 YES입니다.

+과 x 연산에서는 %를 분배법칙처럼 각각의 수에 연산해준 다음 다시 전체를 C로 나누더라도 동일한 값이 출력됩니다.

 

뺄셈의 경우에는 -를 하면서 음수가 나올 수 있기 때문에 음수가 나올수 없도록 아래와 같이 C를 더해줍니다.

A%C가 C보다 작고, B%C가 C보다 작으니 두 수를 빼봤자 C와 같거나 클 수 없고, -C보다 같거나 작을 수 없습니다.

3. (A-B)%C = ((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 << '\n';
    cout << ((a % c) + (b % c)) % c << '\n';
    cout << (a * b) % c << '\n';
    cout << ((a % c) * (b % c)) % c << '\n';
    return 0;
}

 

[결과]

5 8 4
1
1
0
0