Modulo

---

나머지 modulo 연산은 a mod b 에 대해서 0 ~ b 까지의 범위를 가지기 때문에
a 가 매우 큰 값인 경우더라도 적절한 b 의 설정으로 작은 값으로 바꿀 수 있다.

이러한 나머지 연산이 가지는 분배법칙 성질이 있는데 이를 한번 알아보자.

분배 법칙

---

(A + B) % N = ((A % N) + (B % N)) % N

다음의 법칙이 성립한다는 것인데 이를 증명해보면 다음과 같다.

A 와 B에 해당하는 몫과 나머지를 각각 [q1 r1], [q2 r2] 로 가정해보자.
그러면

A = q1 X N + r1 
B = q2 X N + r2

A, B를 나타낼 수 있고 이를 오른쪽 항에 대입하면

(q1 X N + r1 + q2 X N + r2) % N
= ((q1+q2) X N + r1 + r2) % N  

로 치환할 수 있다. 그러면 결국 modulo 는 나머지 연산이기 때문에
몫에 해당하는 q1 와 q2 는 결국 나머지 연산 과정에서 0 이 되어
남는 것은

(r1 + r2) % N

이다. 이때 r1 과 r2 는 위에서 나타낸 대로 대한 A와 B의 나머지이므로
이는 결국

r1 = A % N
r2 = B % N

이 된다. 따라서

(A + B) % N = ((A % N) + (B % N)) % N

이 성립한다는 것을 증명할 수 있다.

같은 방식으로 덧셈 뿐만 아니라 뺄셈, 곱셈에도 마찬가지로 증명할 수 있다.

(A + B) % N = ((A % N) + (B % N)) % N
(A - B) % N = ((A % N) - (B % N)) % N
(A X B) % N = ((A % N) X (B % N)) % N

하지만 나눗셈은 위의 공식에 적용되지 않는다.

그래서 페르마의 소정리를 사용해야 한다는 데 이는 따로 정리해보자!

간단히 생각해보면 A 와 B를 4 , 2 로 N 을 2로 가정하면 0 / 0 꼴이 되므로 공식이 성립될 수 없다. 이를 수학적으로 뭐라고 하는지는... 더 공부해보자!

💻 구현 예시

---

백준 4375번 : 1
https://www.acmicpc.net/problem/4375

문제 해결을 위해 1로만 이루어진 정수에 대한 나머지 연산을 구해야 하는데
n 의 값이 커지면 1로만 이루어진 정수는 엄청난 값으로 커질 수 있기 때문에 이를 막고자
나머지 연산의 분배법칙에서 곱셈에 해당하는 부분을 이용한다.

#include <iostream>

using namespace std;

int main()
{
   int n;
   while(cin >> n)
   {
       int cnt = 1;
       int numberConsistOf1 = 1;
       while(numberConsistOf1 % n != 0)
       {
           numberConsistOf1 = (numberConsistOf1 * 10) % n + 1 % n;
           cnt++;
       }
       cout << cnt << "\n";
   }

   return 0;
}