정수론(Number Theory) (1)
개요
PS에서 정수론은 수학에서 기하와 함께 양대산맥을 이루는 주제중 하나이다.
본 포스트에서는 정수론 알고리즘을 배우기 이전에, 증명 및 이해를 하기 위하여 필수적으로 알아야 할 합동식에 관한 이론과, 정수론에서 가장 기초적인 연산인 모듈러 연산, 기초적인 정수론 알고리즘을 다룬다.
합동식
합동식은 PS에서 사용되는 알고리즘 뿐만 아닌 정수론에서 기본중 기본이 되는 이론이다.
정의
$a, b, m \in \mathbb{Z}$ 에 대하여 $m \mid (a - b)$ 일때 “$a$는 법 $m$에 대하며, $b$와 합동이다” 라고 말한다.
기호로는 다음과 같이 나타낸다.
\[a \equiv b \pmod{m}\]그리고 이는 $x \in \mathbb{Z}$인 임의의 미지수 $x$에 대하여 아래 식과 같은 뜻이 된다.
\[a + mx = b\]성질
합동식에는 9가지 성질이 있는데, 이는 앞으로 배울 알고리즘과, 이론들을 증명할 때 자주 사용되므로 잘 숙지할 필요가 있다.
(추후에 추가 예정)
모듈러 연산
뜻
모듈러 연산은 쉽게 말해 나머지를 구하는 연산이다.
C++는 나머지 연산자 기호를 %로 사용하는데, 아래 예시를 보면 이해가 될 것이다.
1
r = a % m; // 변수 r에는 a를 m으로 나눈 나머지 값이 대입된다.
성질
모듈러 연산에서는 다음과 같은 성질이 사용된다.
- $(a+b) \bmod M \equiv ((a \bmod M) + (b \bmod M)) \bmod M$
- $(a-b) \bmod M \equiv ((a \bmod M) - (b \bmod M + M)) \bmod M$
- $(a\cdot b) \bmod M \equiv ((a \bmod M) \cdot (b \bmod M)) \bmod M$
- $(a\div b) \bmod M \equiv (a \cdot (b^{M-2} \bmod M)) \bmod M$ (단, M은 소수, b와 M은 서로소)
나눗셈에 관한 정리 설명
나눗셈에 관한 정리만을 따로 설명하겠다. 이를 증명하기 위해서는 합동식의 역원 이론과 페르마의 소정리를 알고 있어야 한다.
나눗셈을 사용하는 모듈러 연산자의 경우 타 연산자들과 다르게 아래와 같은 식이 성립되지 않는다.
- $(a \div b) \mod M \equiv ((a \bmod M) \div (b \bmod M))$
(추후에 증명 추가 예정)
$O(\sqrt{x})$ 알고리즘
핵심 아이디어
$2$보다 큰 정수 $x$가 있다고 하였을 때, $2$부터 $\sqrt{x}$보다 작거나 같은 정수들로 나누어 떨어지지 않으면 $x$는 소수라는 것을 활용한다.
$2$보다 큰 양의 정수 $a$와 $b$가 있다고 하였을 때 만약 $a$와 $b$가 둘 다 $\sqrt{x}$보다 커버린다면 $ab > x$가 되어버릴 것이기 때문.
따라서 둘 중 어느 하나가 $\sqrt{x}$보다 커버리면 자동적으로 나머지 하나는 이보다 작을 것이므로, $\sqrt{x}$까지만 확인하여도 $\sqrt{x}$보다 큰 소인수들 또한 구할 수 있는 것을 활용한다.
소수판별
$2$보다 큰 양의 정수 $x$를 소수인지 판별한다고 하자. 이는 $2$부터 $\sqrt{x}$까지의 정수들로 $x$가 나누어 지는지만 확인하면 된다.
1
2
3
4
5
6
bool isPrime(int N) {
for (int i = 2; i * i <= N; i++) {
if (N % i == 0) return false;
}
return true;
}
약수의 개수 세기/찾기
$x$가 $a$의 약수이면 $x/a$ 또한 약수이기 때문에 $\sqrt{x}$까지의 정수들로만 나누어도 $x$의 약수를 전부 찾을 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
int divisorEa(int N) {
int ret = 0;
for (int i = 1; i * i <= N; i++) {
if (N % i == 0) {
if (i * i == N) {
ret += 1;
} else {
ret += 2;
}
}
}
return ret;
}
소인수분해
$x$를 $2$부터 $\sqrt{x}$보다 작거나 같은 정수들 중에서, 나누어 떨어지는 수(소인수)는 나누어 떨어지지 않을 때 까지 계속 나눈 후, $x$가 $1$이면 소인수분해가 된 것이고, $x$가 $1$보다 크다면 해당하는 수 또한 $x$의 소인수이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<pair<int, int>> factorize(int N) {
vector<pair<int, int>> ret;
for(int i = 2; i * i <= N; i++) {
if (N % i == 0) {
ret.push_back({i, 0});
while (N % i == 0) {
ret.back().second++;
N /= i;
}
}
}
if(N != 1) ret.push_back(N, 1)
return ret;
}
에라토스테네스의 체
에라토스테네스의 체는 $2$보다 큰 정수인 $N$보다 작거나 같은 소수들의 목록을 전부 찾는 알고리즘이다.
작동 방식
해당 알고리즘의 핵심은 우선 판단하고 싶은 범위의 수를 전부 소수라고 가정한 후, $2$부터 $\sqrt{N}$까지 하나씩 판단했을 때, 해당 수가 소수라면 해당 배수들에 해당하는 수들을 전부 합성수로 처리해버리는 방식이다.
$\sqrt{N}$까지만 판단하는 이유는 위 소수판별법과 마찬가지로 그 이후의 수를 판단했을 때, 해당 수가 소수라면 그 배수들은 인수가 해당 수를 제외하면 $\sqrt{N}$보다 작은 수로 이루어져 있기 때문에 이미 판단이 끝난 상태이기 때문이다.
마찬가지로 소수로 판단한 수를 $p$라 할 때, 해당 수의 배수를 합성수로 처리할 때 $p^2$부터 처리하는 것이 연산을 더 줄일 수 있다. $p^2$보다 작은 수들은 이미 $p$보다 작은 소수들이 합성수로 처리해 주었기 때문.
구현
$O(NloglogN)$의 시간복잡도로 구현 가능하다.
1
2
3
4
5
6
7
8
9
10
11
12
void sieve(int N) {
vector <bool> isPrime(N + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
}
활용
에라토스테네스의 체는 활용할 수 있는 방법이 다양하다. 대표적으로 다음과 같은 활용법이 있다.
- $2$부터 $N$까지의 자연수에 대하여, 각 수가 인수로 갖는 가장 작은 소인수를 계산
- $2$부터 $N$까지의 자연수에 대하여, 각 수가 갖는 서로 다른 소인수의 개수를 계산
- euler phi function
- 소수에 관한 전처리
유클리드 알고리즘
어떤 정수 $a$와 $b$가 있을 때, 최대공약수인 $gcd(a, b)$를 찾는 알고리즘.
정의
$a \le b$ 를 만복하는 $a, b \in \mathbb{Z}$에 대하여 $gcd(a, b) = gcd(b\mod a, a)$
증명
$a \le b$를 만족한다고 하였을 때 $b$는 다음과 같이 쓸 수 있다. \(b = a\cdot q + r\)
$g\mid a$와 $g\mid b$가 성립한다고 가정하자. 위의 식을 조금만 바꾸어보면 $b - a\cdot q = r$이고, 따라서 아래 식 또한 만족한다. \(g\mid (b - a\cdot q) = r\) 따라서 $g\mid r$이 성립한다.
반대로 $g\mid r$과 $g\mid a$가 만족한다고 가정한 후 위의 $b = r + a\cdot q$로 바꾸어 보면 아래 식이 만족한다. \(g\mid (a\cdot q + r) = b\) 이번엔 반대로 $g\mid b$이 성립한다.
즉, $g$가 $a$와 $b$의 공약수인 것과, $r$과 $a$의 공약수인 것은 동치이다. 공약수 안에 포함되어 있는 최대공약수 또한 동일하다.
핵심 및 연산 횟수
$(a, b)$를 $(r, a)$로 문제를 축소시키는 것이 핵심이다.
이는 문제를 축소시키다 보면 $(0, g)$를 얻는 것이 보장되어 있으므로, 이를 활용하여 $g$의 값을 구할 수 있다.
축소 시킬 때 얼마나 줄어드는지 알아보자.
$a \le b$이므로, $1 \le g$이고, $2r \le (q + 1) r = qr + r \le qa + r = b$ 이다.
따라서 $2r \le b$를 활용하면 $ra \le (1/2)ab$ 이므로 한번 문제를 축소할 때 마다 최소 절반씩 줄일 수 있다.
구현
재귀적인 방법으로 간단히 구현 가능하다.
1
2
3
4
5
int gcd(int a, int b) {
if (a > b) return gcd(b, a);
if (a == 0) return b;
return gcd(b % a, a);
}