[백준] 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를 출력한다.

---

풀이

모듈러 연산(Modular Arithmethic)

 

1) n|a

    : a는 n의 배수이다.

​

2) a mod n

    : a를 n으로 나눈 나머지 값

   

    ex)

    12 mod 3 = 0

    18 mod 7 = 4

    9 mod 9 = 0

    -25 mod 11 = 8

​

3) 합동관계

a mod n=b mod n이라면 a mod n=b mod n이라면 a ≡ b (mod n)​ a 와 b를 modul c 에 관한 합동관계라 한다.

​

n|a 이고 n|b 이므로 이는 a = n*k , b = n*r 로 표현이 가능하다. 이로 인해 다음과 같은 성질을 나타낼수 있다.

    1. a ≡ b (mod n) if (a−b)는 n의 배수​

    2. a ≡ b (mod n) implies b ≡ a(mod n)​

    2. a ≡ b (mod n) and b ≡ c (mod n) implies a ≡ c(mod n)​

 

4) 성질

    1. (a+b) mod n = ((a mod n)+(b mod n)) mod n​

    2. (a−b) mod n = ((a mod n)−(b mod n)) mod n​

    3. (a·b) mod n = ((a mod n)·(b mod n)) mod n​

​

5) 페르마의 소정리

​

6) 확장 유클리드 알고리즘

 

코드