1 2 3 4 5 6 7 8 | #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; } | cs |
처음 이 문제를 풀 때만해도 그렇게까지 의미있는 문제인지 몰랐지ㅎㅎ
나머지 연산에 대해 이해 잘 해놓자ㅠㅠ
<나머지>
- 주로 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를 구해야함)
'백준 1 > 수학' 카테고리의 다른 글
| [백준 2292] 벌집 (C++/Python) (0) | 2020.12.06 |
|---|---|
| [백준 11070] 피타고라스 기댓값 (0) | 2020.12.06 |
| [백준 1373] 2진수 8진수 (0) | 2020.12.06 |
| [백준 1110] 더하기 사이클 (0) | 2020.12.06 |
| [백준 1712] 손익분기점 (0) | 2020.12.06 |