나머지 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
하지만 나눗셈은 위의 공식에 적용되지 않는다.
그래서 페르마의 소정리를 사용해야 한다는 데 이는 따로 정리해보자!
백준 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;
}