Mobius Function, Mobius Inversion

mobius-inversion, Mobius Function, Mobius Inversion, 뫼비우스 함수, 뫼비우스 역원, Dirichlet Convolution

정의

Mobius Function μ(n) 은 양의 정수에 대한 수론 함수:

μ(1) = 1
μ(n) = (-1)^k  if n = p_1 · p_2 · ... · p_k (서로 다른 소수의 곱)
μ(n) = 0       if n 이 어떤 소수의 제곱을 인수로 가짐

Mobius Inversion (뫼비우스 역원) 은 합 / 컨볼루션 관계의 역변환. PS 에서는 GCD / 서로소 카운팅 의 표준 도구.

문제 상황과 동기

GCD / 서로소 카운팅 문제는 순진하게 O(N²) 또는 O(N² log N). 예를 들어 “1 ≤ i, j ≤ N, gcd(i, j) = 1 인 쌍의 수” 는 이중 루프로 O(N² log N) 이지만, Mobius 함수를 이용하면 Σ_d μ(d) · floor(N/d)² 로 정리되어 floor division blocking 기법으로 O(√N) 또는 O(N) 에 풀린다.

핵심 아이디어: [gcd(i, j) = 1] = Σ_{d | gcd(i, j)} μ(d) 라는 항등식. 합의 순서를 뒤집으면 Σ_d μ(d) · (N/d 의 배수 쌍 수) 꼴로 바뀌어 d 별로 O(1) 에 카운팅할 수 있다.

PS 에서는 GCD 조건을 뫼비우스 합으로 분해 → floor division blocking 으로 O(√N) 패턴이 정형. Dirichlet convolution 의 역원 성질을 이용해 약수 합 관계를 역변환 하는 것도 자주 등장.

문제 상황과 동기

Σ_{i=1..N} Σ_{j=1..N} [gcd(i,j) = 1] 같은 서로소 쌍 카운팅은 naive double loop 로 O(N² log N). N ≥ 10^6 이면 불가능.

Mobius function 과 floor(N/d) blocking 을 결합하면 이런 식을 O(√N) 로 줄일 수 있다. 핵심은 gcd 조건을 약수 합으로 바꾼 뒤 inversion 으로 역산하는 것. PS 에서 GCD 합 / 서로소 카운팅 / squarefree 집합 등이 이 트릭 없이는 풀 수 없다.

이 패턴은 Dirichlet Convolution 과 Euler Phi 와도 밀접하다. 셋을 묶어서 “Mobius 계열 수론 트릭” 으로 부르기도 한다.

시각화

시각화

핵심 공식

Dirichlet Convolution

(f * g)(n) = Σ_{d | n} f(d) · g(n/d)

이 곱셈 환에서 μ 와 상수함수 1 은 서로 역원.

1 * μ = ε   (where ε(1) = 1, ε(n>1) = 0)

Mobius Inversion

f(n) = Σ_{d | n} g(d)  ⇔  g(n) = Σ_{d | n} μ(n/d) · f(d)

또는 덮개 (cover) 버전:

f(n) = Σ_{n | d} g(d)  ⇔  g(n) = Σ_{n | d} μ(d/n) · f(d)

핵심 응용

1. 서로소 카운팅

Σ_{i=1..N} Σ_{j=1..N} [gcd(i,j) = 1] = Σ_{d=1..N} μ(d) · floor(N/d)²

2. GCD 합 / LCM 합

Σ Σ gcd(i, j) = Σ_d φ(d) · floor(N/d)² 또는 mobius 로 직접.

Σ Σ lcm(i, j) = (i·j / gcd(i,j)) 의 합.

3. Coprime Integers 카운팅

Σ [gcd(a, b) = 1, 1 ≤ a ≤ A, 1 ≤ b ≤ B].

4. Square-free 카운팅

[n 이 squarefree] = |μ(n)|.

구현

선형 체로 μ 계산

// O(N) 선형 체. μ[1..N] 를 모두 계산.
#include <vector>
using namespace std;

vector<int> compute_mobius(int N) {
    vector<int> mu(N + 1, 1);
    vector<bool> is_prime(N + 1, true);
    vector<int> primes;

    for (int i = 2; i <= N; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            mu[i] = -1; // 한 개 소수
        }
        for (int p : primes) {
            if ((long long)i * p > N) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                mu[i * p] = 0; // p^2 인수 포함
                break;
            } else {
                mu[i * p] = -mu[i]; // 소수 한 개 추가
            }
        }
    }
    return mu;
}

서로소 쌍 카운팅 예시

// Σ_{1 ≤ i,j ≤ N} [gcd(i,j) = 1] 를 O(√N) 에 계산.
// blocking 으로 floor(N/d) 가 같은 구간 묶음.
#include <vector>
using namespace std;

long long coprime_count(int N) {
    auto mu = compute_mobius(N);
    long long ans = 0;
    
    // Σ_{d=1..N} μ(d) · ⌊N/d⌋²
    for (int d = 1; d <= N; ) {
        long long q = N / d;
        int next_d = N / q + 1;
        
        // d ~ (next_d-1) 구간에서 floor(N/d) = q 가 고정
        long long mu_sum = 0;
        for (int x = d; x < next_d && x <= N; x++) {
            mu_sum += mu[x];
        }
        ans += mu_sum * q * q;
        d = next_d;
    }
    return ans;
}

작은 입력 step trace

N = 4 일 때, Σ_{i,j=1..4} [gcd(i,j) = 1]

μ = [-, 1, -1, -1, 0]  (인덱스 0 무시)

Σ_{d=1..4} μ(d) · ⌊4/d⌋²
  = μ(1)·16 + μ(2)·4 + μ(3)·1 + μ(4)·1
  = 1·16 + (-1)·4 + (-1)·1 + 0·1
  = 16 - 4 - 1 = 11

실제로 (1,1), (1,2), (1,3), (1,4), (2,1), (2,3),
(3,1), (3,2), (3,4), (4,1), (4,3) = 11 쌍

응용 패턴

Σ_{i,j} f(gcd(i,j)) 같은 식을 풀 때:

Σ_{i,j} f(gcd(i,j))
  = Σ_d f(d) · # of (i,j) with gcd(i,j) = d
  = Σ_d f(d) · Σ_{k} μ(k) · floor(N/(d·k))²

이중 합을 blocking (floor(N/x) 가 같은 x 들을 묶음) 으로 O(N^0.6666666666666666) 또는 O(√N).

복잡도

작업	비용
μ 선처리	O(N)
단일 평가 (소인수분해)	O(√n)
합 식 1회 (blocking)	O(√N)

함정

1. μ(n) = 0 케이스

squarefree 가 아니면 0. 합에서 자연스럽게 무시되지만 항을 일일이 더하면 정확.

2. 합의 인덱스 범위

Σ_{d | n} vs Σ_{n | d}. 어느 쪽 합인지에 따라 inversion 공식이 다름.

3. 음수 mod

μ 는 -1 을 포함. mod p 에서 μ(n) ≡ p - 1 (if μ = -1) 로 처리.

4. φ (Euler totient) 와 혼동

φ 도 자주 같이 등장. Σ_{d|n} φ(d) = n, φ * 1 = id. 서로 다른 함수.

BOJ 연습 문제

번호	제목	링크
BOJ 16409	Coprime Integers	kokoa-lab
BOJ 14860	GCD 곱	kokoa-lab
BOJ 11691	LCM(i, j)	kokoa-lab
BOJ 14861	LCM 더하기	kokoa-lab

참고

• FWHT
• Generating Function
• Stern-Brocot Tree