황소개발자

(a + b) % c 는 (a % c + b % c) % c 와 같으며 곱셈연산에 있어서도 성립한다. 나누기 연산은 (a / b) % c 는 (a * b ^ (c - 2)) % c --- a와 b는 서로소, c는 소수 (페르마의 소정리) 와 같으며 빼기 연산은 (a - b) % c 는 (a % c - b % c + c) % c 와 같다 알고리즘문제에 있어 모듈(나머지) 연산은 오버플로우 방지에 필수다.

이 문제는 정말 쉬우나 알고리즘은 중요하다. 나중에 "10007로 나눈 나머지를 구하세요" 라고 묻는 문제들이 종종보이는데 마지막에 모듈연산을 해줘야할 뿐 아니라 계산 과정중에서도 모듈연산을 해도 괜찮다는 증거의 알고리즘이기 때문이다. 그래서 결국 오버플로우를 막으면서 연산이 가능하게 된다. import sys input = 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)