[백준][파이썬] 10430번_나머지

문제

(A+B)%C는 ((A%C) + (B%C))%C 와 같을까?
(A×B)%C는 ((A%C) × (B%C))%C 와 같을까?
세 수 A, B, C가 주어졌을 때, 위의 네 가지 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)

출력

첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다.

입력 예제

5 8 4

출력 예제

1
1
0
0

소스코드

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)

---

(A*B)%C = ((A%C) * (B%C))%C 증명

• mod 연산자에 대한 분배법칙은 성립하지 않는다. 즉, (a+b)%c != (a%c + b%c)
• 모듈러 연산에 관한 어떤 성질을 증명하고자 할 때 종종 나머지 정리를 이용
• 나머지 정리 : 어떤 정수에서 A와 양의 정수 B가 주어질 때 다음을 만족하는 유일한 정수 Q와 R이 존재한다
• (A * B) mod C = (A mod C * B mod C) mod C
  • A = C * Q1 + R1 이때 0 ≤ R1 < C 이고 Q1는 정수이다. A mod C = R1
    B = C * Q2 + R2 이때 0 ≤ R2 < C이고 Q2 는 정수이다.B mod C = R2
  • ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C = (R1 * R2 ) mod C
    (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1)  + R1 * R 2 )  mod C = (R1 * R2) mod C
    
  • mod C로 정리하면 C의 배수를 없앨 수 있다
    (R1 * R2) mod C = (R1 * R2) mod C
    

참고 : https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-multiplication

•  

•