← 다이아몬드 I

뫼비우스 반전

약수 합 관계를 뒤집어 카운팅을 정리한다.

수학

다이아몬드 I

선수 지식: 에라토스테네스의 체

1강 약수 관계 뒤집기: 뫼비우스 반전 공식

뫼비우스 함수

$\mu(n) = \begin{cases} 1 & n=1 \\ (-1)^k & n = p_1 p_2 \cdots p_k\ (\text{서로 다른 소수}) \\ 0 & p^2 \mid n \end{cases}$

핵심 성질은 디리클레 합

$\sum_{d \mid n} \mu(d) = [\,n = 1\,].$

이 한 줄이 모든 뫼비우스 반전의 엔진이다.

뫼비우스 반전 공식

두 산술함수 $$f, g$$ 가

$g(n) = \sum_{d \mid n} f(d)$

관계이면, 이를 뒤집어

$f(n) = \sum_{d \mid n} \mu(d)\, g\!\left(\tfrac{n}{d}\right)$

를 얻는다. 약수 합으로 정의된 양에서 원래 양을 복원하는 도구다. 디리클레 합성곱으로 보면 $g = f * \mathbf{1}$ 이고 $\mathbf{1}^{-1} = \mu$ 이므로 $f = g * \mu$ .

정수론적 카운팅의 표준 변형

자주 쓰는 형태는 "조건이 gcd로 걸린 합"이다.

$\sum_{i=1}^{n}\sum_{j=1}^{m} [\gcd(i,j)=1] = \sum_{i,j} \sum_{d \mid \gcd(i,j)} \mu(d) = \sum_{d=1}^{\min(n,m)} \mu(d) \left\lfloor \tfrac{n}{d} \right\rfloor \left\lfloor \tfrac{m}{d} \right\rfloor.$

$[\gcd=1] = \sum_{d\mid \gcd}\mu(d)$ 를 대입하고 합의 순서를 바꾸는 것이 정석. 일반화하면 $\gcd = k$ 조건은 $$i,j$$ 를 $$k$$ 로 나눠 위 식으로 환원한다.

정수 나눗셈 블록(divisor blocks)

$\lfloor n/d \rfloor$ 는 서로 다른 값이 $O(\sqrt n)$ 개뿐이다. 같은 값을 갖는 $$d$$ 구간을 묶으면

$\sum_{d=1}^{n} f(d)\, g\!\left(\lfloor n/d\rfloor\right)$

를 $\mu$ 의 전구간 합(prefix sum)과 결합해 $O(\sqrt n)$ 에 계산한다. 이것이 "뫼비우스 + 블록 분할" 콤보.

복잡도

작업	비용
$\mu$ 선형 체로 전부	$$O(N)$$
gcd 카운팅 직접 합	$O(\min(n,m))$
블록 분할 결합	$O(\sqrt n)$ (전처리 후)

2강 뫼비우스 구현과 응용 공식

선형 체로 $\mu$ 와 prefix sum

#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
int mu[N + 1], primes[N], pc;
bool comp[N + 1];
long long mu_pre[N + 1];      // mu의 누적합

void sieve() {
    mu[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!comp[i]) { primes[pc++] = i; mu[i] = -1; }
        for (int j = 0; j < pc && (long long)i * primes[j] <= N; j++) {
            comp[i * primes[j]] = true;
            if (i % primes[j] == 0) { mu[i * primes[j]] = 0; break; }
            mu[i * primes[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= N; i++) mu_pre[i] = mu_pre[i - 1] + mu[i];
}

서로소 쌍 개수 (블록 분할)

$\sum_{i\le n}\sum_{j\le m}[\gcd(i,j)=1] = \sum_d \mu(d)\lfloor n/d\rfloor\lfloor m/d\rfloor$ 를 $O(\sqrt{})$ 에.

long long coprime_pairs(int n, int m) {
    if (n > m) swap(n, m);
    long long ans = 0;
    for (int d = 1, nd; d <= n; d = nd + 1) {
        nd = min(n / (n / d), m / (m / d));        // 같은 (n/d),(m/d) 블록 끝
        long long muSum = mu_pre[nd] - mu_pre[d - 1];
        ans += muSum * (long long)(n / d) * (m / d);
    }
    return ans;
}

자주 하는 실수

선형 체의 $\mu$ 전파. i % p == 0 이면 $\mu(i\cdot p)=0$ 이고 break. 그렇지 않으면 부호 반전. 이 분기를 정확히.
블록 끝 계산. 두 변수 버전은 min(n/(n/d), m/(m/d)) 로 두 블록의 공통 끝을 잡는다.
prefix sum 부호. $\mu$ 의 누적합은 음수가 될 수 있으니 long long.
gcd=k 일반화. $$i=ki', j=kj'$$ 로 치환하면 $\lfloor n/k\rfloor, \lfloor m/k\rfloor$ 범위의 서로소 쌍 문제로 환원.

응용

문제	변형
$\sum[\gcd=1]$	$\mu$ 직접
$\sum \gcd(i,j)$	$\sum_d \phi(d)\cdot(\dots)$ 또는 $\mu$ + 약수합
$\sum \mathrm{lcm}$	$ij/\gcd$ 전개 후 반전
무제곱수 개수	$\sum_d \mu(d)\lfloor N/d^2\rfloor$

디리클레 합성곱 시야

$\mu$ 는 항등 $\mathbf{1}$ 의 디리클레 역원이다. $\phi = \mu * \mathrm{id}$ , $\mathrm{id} = \phi * \mathbf{1}$ 등 표준 관계를 외워 두면, 새로운 정수론 합도 합성곱 분해 → 반전으로 기계적으로 정리된다. 더 큰 합은 두엔 분(Du sieve)으로 $O(N^{2/3})$ 까지 낮춘다.