정수 분할 기법 (Divisor Summation)
형태가 \(\sum_{i=1}^{n} f(i) \cdot g\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\)인 합을 효율적으로 계산하는 방법입니다. \(g(x)\)와 구간 합 \(\sum_{i=l}^{r} f(i)\)를 빠르게 구할 수 있을 때 유용합니다.
핵심 원리
\(\left\lfloor\frac{n}{i}\right\rfloor\) 값이 같은 구간들을 묶어서 한 번에 처리합니다. 이 값의 종류는 \(O(\sqrt{n})\) 개에 한정됩니다.
구간 끝점 계산: 왼쪽 끝 \(l\)이 주어졌을 때, 오른쪽 끝 \(r\)은 다음과 같이 구합니다:
구현 예시
long long divisorSum(long long n) {
long long total = 0;
for (long long left = 1, right = 0; left <= n; left = right + 1) {
right = n / (n / left);
total += (right - left + 1) * (n / left);
}
return total;
}다중 변수 확장
\(\sum_i f(i) \prod_{j=1}^{k} g_j\left(\left\lfloor\frac{n_j}{i}\right\rfloor\right)\) 형태에서는:
복잡도는 \(O(k\sqrt{n})\)입니다.
선형 체 (Linear Sieve)
\(O(n)\) 시간에 모든 소수와 다양한 적성 함수 값을 계산하는 알고리즘입니다.
핵심 성질
- 각 합성수는 가장 작은 소인수에 의해 한 번만 제거됨
i % prime == 0에서 중단하여 중복 제거 방지
vector<int> primes;
vector<bool> isComp(MAXN);
void linearSieve(int n) {
for (int i = 2; i <= n; i++) {
if (!isComp[i]) primes.push_back(i);
for (int p : primes) {
if (i * p > n) break;
isComp[i * p] = true;
if (i % p == 0) break; // p가 i의 최소 소인수
}
}
}적성 함수 계산 패턴
함수 \(f\)를 계산할 때 세 가지 경우를 처리:
- \(n \in \mathbb{P}\): 보통 간단한 형태
- \(p \nmid n\): \(f(np) = f(n) \cdot f(p)\) (적성 활용)
- \(p \mid n\): \(n = a \cdot p^k\)로 분해하여 관계식 유도
오일러 토션트 함수 예시
\(n = a \cdot p^k\) (\(\gcd(a,p)=1\))일 때:
vector<int> phi(MAXN);
void sievePhi(int n) {
for (int i = 2; i <= n; i++) {
if (!isComp[i]) {
primes.push_back(i);
phi[i] = i - 1;
}
for (int p : primes) {
if (i * p > n) break;
isComp[i * p] = true;
if (i % p == 0) {
phi[i * p] = phi[i] * p; // p | i인 경우
break;
}
phi[i * p] = phi[i] * (p - 1); // p ∤ i인 경우
}
}
}뫼비우스 반전 (Möbius Inversion)
뫼비우스 함수
핵심 정리
따라서: \([\gcd(a,b) = 1] = \sum_{d|\gcd(a,b)} \mu(d)\)
반전 공식
디리클레 합성곱 관점: \(f = g * 1 \Rightarrow g = \mu * f\)
응용: GCD 관련 합
\(\sum_{x=1}^{a}\sum_{y=1}^{b} [\gcd(x,y) = d]\) 계산:
long long coprimePairs(int a, int b, int d) {
a /= d; b /= d;
int limit = min(a, b);
long long res = 0;
for (int l = 1, r = 0; l <= limit; l = r + 1) {
r = min(a / (a / l), b / (b / l));
res += 1LL * (muPrefix[r] - muPrefix[l-1]) * (a / l) * (b / l);
}
return res;
}두 교수 알고리즘 (Du Jiao Sieve)
적성 함수의 부분합 \(S(n) = \sum_{i=1}^{n} f(i)\)를 \(O(n^{2/3})\) 이하로 계산하는 기법입니다.
핵심 항등식
따라서:
적용 예시
| 목표 | 선택한 \(g\) | \(f * g\) |
|---|---|---|
| \(\sum_{i=1}^{n} \mu(i)\) | \(1(n) = 1\) | \(\varepsilon\) |
| \(\sum_{i=1}^{n} \varphi(i)\) | \(1(n) = 1\) | \(\text{Id}\) |
unordered_map<long long, long long> cache;
long long sumMu(long long n) {
if (n <= PRE) return muPrefix[n];
if (cache.count(n)) return cache[n];
long long ans = 1; // sum of epsilon
for (long long l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
ans -= (r - l + 1) * sumMu(n / l);
}
return cache[n] = ans;
}강력한 수筛 (Powerful Numbers Sieve)
모든 소인자의 지수가 \(\geq 2\)인 수(강력한 수)를 이용한 부분합 계산 기법입니다.
핵심 사실
\(\leq n\)인 강력한 수의 개수는 \(O(\sqrt{n})\)입니다.
적용 조건
적성 함수 \(f\)에 대해:
- \(f(1) = 1\)
- \(g(p) = f(p)\)이고 \(S_g\)를 쉽게 계산할 수 있는 \(g\) 존재
\(h = f * g^{-1}\)로 정의하면 \(h(p) = 0\)이므로, \(h\)는 강력한 수에서만 0이 아닙니다.
유클리드 유사 알고리
\(f(n, a, b, c) = \sum_{i=0}^{n} \left\lfloor\frac{ai+b}{c}\right\rfloor\)를 \(O(\log n)\)에 계산합니다.
재귀 단계
\(a \geq c\) 또는 \(b \geq c\)인 경우:
그 외의 경우 (\(a, b < c\)):
여기서 \(m = \left\lfloor\frac{an+b}{c}\right\rfloor\)
long long floorSum(long long n, long long a, long long b, long long c) {
if (a == 0) return (n + 1) * (b / c);
if (a >= c || b >= c) {
return (a / c) * n * (n + 1) / 2
+ (b / c) * (n + 1)
+ floorSum(n, a % c, b % c, c);
}
long long m = (a * n + b) / c;
return n * m - floorSum(m - 1, c, c - b - 1, a);
}치폴라 알고리즘 (Cipolla's Algorithm)
홀수 소수 \(p\)에 대해 \(x^2 \equiv a \pmod{p}\)의 해를 구합니다.
오일러 판별법
결과가 \(1\)이면 이차잉여, \(-1\)이면 이차비잉여입니다.
알고리즘
- \(b^2 - a\)가 이차비잉여인 \(b\)를 무작위로 탐색 (기대 2회)
- 허수 단위 \(i\)를 \(i^2 \equiv b^2 - a \pmod{p}\)로 정의
- 해는 \(x \equiv (b+i)^{\frac{p+1}{2}} \pmod{p}\)
복잡도: \(O(\log p)\)
행렬 기초
기본 연산
- 덧셈/뺄셈: 대응 원소별 연산
- 스칼라 곱: 모든 원소에 스칼라 곱
- 곱셈: \(C_{i,j} = \sum_{k} A_{i,k} \cdot B_{k,j}\)
행렬 곱셈은 결합법칙과 분배법칙을 만족하나 교환법칙은 만족하지 않습니다.
가우스 소거법
기본 행 연산을 통해 행렬을 상삼각 형태로 변환:
- 각 열에서 피봇(주원소) 선택
- 피봇 행을 해당 열의 최상단으로 이동
- 피봇 아래의 모든 원소를 0으로 만듦
가우스-조던 소거법: 피봇 위아래 모두 0으로 만들어 대각 행렬로 변환
선형 방정식 풀이
계수 행렬 \(A\)와 상수 벡터 \(\mathbf{b}\)로 확장 행렬 \([A|\mathbf{b}]\)를 구성하여 소거법 적용
선형 공간
기저와 차원
벡터 집합 \(S\)의 모든 선형결합으로 생성되는 공간을 \(\operatorname{span}(S)\)라 합니다.
- 선형독립: 어떤 벡터도 다른 벡터들로 표현 불가
- 기저: \(V\)를 생성하는 선형독립 합
- 차원: 기저의 크기, \(\dim V\)
이진 선형 기저
\(\mathbb{F}_2\) 위에서의 선형 기저로, XOR 관련 문제에 활용됩니다.
struct LinearBasis {
long long basis[64];
void insert(long long x) {
for (int i = 63; i >= 0; i--) {
if (!(x >> i & 1)) continue;
if (!basis[i]) { basis[i] = x; break; }
x ^= basis[i];
}
}
long long queryMax() {
long long res = 0;
for (int i = 63; i >= 0; i--)
if ((res ^ basis[i]) > res) res ^= basis[i];
return res;
}
};행렬식
\(n\)차 정방행렬 \(A\)의 행렬식:
기하학적 의미: 열 벡터가 이루는 유향 부피
가우스 소거법을 이용한 계산: 소거 과정에서 행 교환 시 부호 반전, 행 배수 시 그 배수로 곱함
생성함수 개요
수열 \(a_0, a_1, a_2, \ldots\)를 형식적 거듭제곱급수 \(A(x) = \sum_{n \geq 0} a_n x^n\)로 표현합니다.
일반적인 생성함수 (OGF)
| 수열 | 생성함수 |
|---|---|
| \(1, 1, 1, \ldots\) | \(\frac{1}{1-x}\) |
| \(1, 2, 3, \ldots\) | \(\frac{1}{(1-x)^2}\) |
| \(\binom{n}{k}\) | \((1+x)^n\) |
| 카탈란 수 | \(\frac{1-\sqrt{1-4x}}{2x}\) |
지수 생성함수 (EGF)
EGF의 곱셈은 라벨링된 구조의 조합에 대됩니다.
주요 연산
- 덧셈: \(A(x) + B(x)\) → 대응 원소별 덧셈
- 곱셈: \(A(x) \cdot B(x)\) → 디리클레 합성곱/컨볼루션
- 역원: \(A(x) \cdot A^{-1}(x) = 1\)
- 미분/적분: 수열의 이동과 관련
FFT를 이용한 다항식 곱셈
using cd = complex<double>;
const double PI = acos(-1);
void fft(vector<cd>& a, bool invert) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (invert ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int j = 0; j < len / 2; j++) {
cd u = a[i+j], v = a[i+j+len/2] * w;
a[i+j] = u + v;
a[i+j+len/2] = u - v;
w *= wlen;
}
}
}
if (invert) {
for (cd & x : a) x /= n;
}
}복잡도: \(O(n \log n)\)