1. 기초 연산 및 약수와 배수
1.1 나머지 연산 (Modular Arithmetic)
나머지 연산은 다음과 같은 분배 법칙이 성립합니다.
- $(a + b) \pmod c = ((a \pmod c) + (b \pmod c)) \pmod c$
- $(a - b) \pmod c = ((a \pmod c) - (b \pmod c) + c) \pmod c$
- $(a \times b) \pmod c = ((a \pmod c) \times (b \pmod c)) \pmod c$
1.2 약수와 배수 (Divisibility)
정수 $a, b$에 대해 $b = a \times c$를 만족하는 정수 $c$가 존재하면 $a$는 $b$를 나누며, 이를 $a \mid b$라고 표기합니다. 이때 $a$는 $b$의 약수, $b$는 $a$의 배수입니다.
- $a \mid b$ 이고 $b \mid c$ 이면 $a \mid c$ 입니다.
- $a \mid b$ 이고 $b \mid a$ 이면 $|a| = |b|$ 입니다.
2. 최대공약수 (GCD)
2.1 유클리드 호제법
가장 널리 쓰이는 알고리즘으로 시간 복잡도는 $O(\log n)$입니다.
long long get_gcd(long long n1, long long n2) {
while (n2 != 0) {
n1 %= n2;
long long temp = n1;
n1 = n2;
n2 = temp;
}
return n1;
}
2.2 Binary GCD (Stein's Algorithm)
나눗셈 연산 없이 비트 연산만으로 GCD를 구하여 효율성을 높인 방식입니다.
int fast_gcd(int x, int y) {
if (!x || !y) return x | y;
int shift = __builtin_ctz(x | y);
x >>= __builtin_ctz(x);
while (y) {
y >>= __builtin_ctz(y);
if (x > y) {
int temp = x;
x = y;
y = temp;
}
y -= x;
}
return x << shift;
}
3. 거듭제곱과 소수
3.1 빠른 거듭제곱 (Binary Exponentiation)
분할 정복을 이용하여 $a^b \pmod p$를 $O(\log b)$ 시간에 계산합니다.
long long power_mod(long long base, long long exp, long long mod) {
long long res = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return res;
}
3.2 소수 판별: 밀러-라빈 (Miller-Rabin)
큰 수에 대해 확률적으로 소수 여부를 판별하는 알고리즘입니다.
bool miller_rabin(long long n, long long a) {
if (a % n == 0) return true;
long long d = n - 1;
while (d % 2 == 0) {
if (power_mod(a, d, n) == n - 1) return true;
d /= 2;
}
long long res = power_mod(a, d, n);
return res == n - 1 || res == 1;
}
bool check_prime(long long n) {
static const long long bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
for (long long a : bases) {
if (n == a) return true;
if (!miller_rabin(n, a)) return false;
}
return true;
}
4. 약수의 성질과 선형 체
4.1 약수의 개수와 합
$n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$일 때:
- 약수의 개수: $d(n) = \prod (e_i + 1)$
- 약수의 총합: $\sigma(n) = \prod \frac{p_i^{e_i+1}-1}{p_i-1}$
4.2 오일러 피 함수 (Euler's Totient Function)
$\varphi(n)$은 $n$ 이하의 자연수 중 $n$과 서로소인 수의 개수입니다.
int get_phi(int n) {
int res = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
res = res / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) res = res / n * (n - 1);
return res;
}
5. 합동식과 모듈러 역원
5.1 페르마의 소정리
$p$가 소수이고 $a$가 $p$의 배수가 아닐 때, $a^{p-1} \equiv 1 \pmod p$ 이므로 역원은 $a^{p-2} \pmod p$입니다.
5.2 선형 역원 계산
1부터 $n$까지의 모든 역원을 $O(n)$ 시간에 구하는 방법입니다.
void precompute_inverses(int n, int p) {
inv[1] = 1;
for (int i = 2; i <= n; i++) {
inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}
}
6. 확장 유클리드 알고리즘 (exgcd)
$ax + by = \gcd(a, b)$를 만족하는 정수해 $x, y$를 구합니다.
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
long long x1, y1;
long long d = extended_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
7. BSGS (Baby-step Giant-step)
$a^x \equiv b \pmod p$에서 $x$를 구하는 알고리즘으로 $O(\sqrt{p})$의 시간이 소요됩니다.
long long solve_bsgs(long long a, long long b, long long p) {
a %= p; b %= p;
if (b == 1) return 0;
long long m = ceil(sqrt(p));
unordered_map<long long, long long> baby_steps;
long long cur = b;
for (int j = 0; j < m; j++) {
baby_steps[cur] = j;
cur = (cur * a) % p;
}
long long giant = power_mod(a, m, p);
cur = giant;
for (int i = 1; i <= m; i++) {
if (baby_steps.count(cur)) {
return i * m - baby_steps[cur];
}
cur = (cur * giant) % p;
}
return -1;
}
8. 가우스 소거법 (Gaussian Elimination)
선형 방정식 시스템을 상삼각 행렬로 변환하여 해를 구합니다.
int solve_gauss(vector<vector<double>> &matrix, int n, vector<double> &result) {
for (int i = 0; i < n; i++) {
int pivot = i;
for (int j = i + 1; j < n; j++)
if (abs(matrix[j][i]) > abs(matrix[pivot][i])) pivot = j;
swap(matrix[i], matrix[pivot]);
if (abs(matrix[i][i]) < 1e-9) continue;
for (int j = 0; j < n; j++) {
if (i != j) {
double factor = matrix[j][i] / matrix[i][i];
for (int k = i; k <= n; k++)
matrix[j][k] -= factor * matrix[i][k];
}
}
}
for (int i = 0; i < n; i++) {
if (abs(matrix[i][i]) < 1e-9 && abs(matrix[i][n]) > 1e-9) return 0; // 무해
result[i] = matrix[i][n] / matrix[i][i];
}
return 1;
}
9. 행렬 거듭제곱과 점화식
피보나치 수열과 같은 선형 점화식은 행렬 거듭제곱을 통해 $O(\log n)$ 시간에 계산할 수 있습니다.
피보나치 수열 변환 행렬: $\begin{bmatrix} f_{n} \\ f_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f_{n-1} \\ f_{n-2} \end{bmatrix}$