[백준 10430] 나머지

#include<stdio.h>
int main(void)
{
    int a,b,c;
    scanf("%d %d %d", &a, &b, &c);
    printf("%d\n%d\n%d\n%d", (a+b)%c, ((a%c)+(b%c))%c, (a*b)%c, (a%c*b%c)%c);
    return 0;
}

처음 이 문제를 풀 때만해도 그렇게까지 의미있는 문제인지 몰랐지ㅎㅎ

나머지 연산에 대해 이해 잘 해놓자ㅠㅠ

<나머지>

- 주로 DP에 사용

- 경우의 수를 구하는 문제에서 경우의 수가 너무 클 때

- 매번 구하면서 나머지 연산 수행하기

1 2 3 4 5 6 7 8 9 10 11 12 13 14

A=q1c+r1 B=q2c+r2   A+B=(q1+q2)*c+(r1+r2) (A+B)%c=(r1+r2)%c       A%C=r1 +) B%C=r2 ______________ (A%C+B%C)=(r1+r2)   (A%C+B%C)%c=(r1+r2)%c   => (A+B)%c == (A%C+B%C)%c

cs

- (A+B)%m=((A%m)+(B%m))%m

- (A*B)%m=((A%m)*(B%m))%m

- 뺄셈의 경우 먼저 나눗셈 연산을 한 결과가 음수가 나올 수 있으므로 아래처럼 해야함

- (A-B)%m=((A%m)-(B%m)+m) %m

- 나누기는 성립하지 않는다. (Modular Inverser를 구해야함)