# Multiplicative Functions

Multiplicative Functions는 `gcd(a, b)=1`일 때 `f(ab)=f(a)f(b)`를 만족하는 산술 함수입니다. Euler phi, Mobius function, divisor count, divisor sum처럼 정수론 문제에서 반복되는 함수들을 linear sieve로 한 번에 계산할 수 있습니다.

## 문제 신호

| 문제 표현 | Multiplicative Function 관점 |
| --- | --- |
| 모든 `n <= N`에 대해 `phi(n)`, `mu(n)` 필요 | linear sieve |
| 약수 개수나 약수 합을 많이 물어봄 | prime power 상태 관리 |
| gcd가 1인 곱에서 값이 분리됨 | multiplicativity |
| `n = p^k * rest` 구조로 갱신 가능 | least prime factor DP |
| Dirichlet convolution 결과 함수 필요 | multiplicative closure |

함수가 multiplicative이면 모든 수를 직접 factorization하지 않고 sieve 순서에서 값을 채울 수 있습니다.

## Multiplicative와 Completely Multiplicative

두 개념은 다릅니다.

| 종류 | 조건 | 예 |
| --- | --- | --- |
| multiplicative | `gcd(a,b)=1`일 때만 `f(ab)=f(a)f(b)` | `phi`, `mu`, `tau`, `sigma` |
| completely multiplicative | 모든 `a,b`에서 성립 | `f(n)=n^k`, 일부 character |

대부분의 산술 함수는 multiplicative일 뿐입니다. 예를 들어 `phi(p^2)`는 `phi(p)^2`가 아닙니다.

multiplicative 함수는 f(1)=1입니다.

## Prime Power 공식

Multiplicative function은 prime power 값만 알면 전체 값을 조립할 수 있습니다.

| 함수 | `p^k`에서 값 |
| --- | --- |
| `phi(n)` | `p^k - p^(k-1)` |
| `mu(n)` | `-1` if `k=1`, `0` if `k>=2` |
| `tau(n)` | `k + 1` |
| `sigma(n)` | `1 + p + ... + p^k` |

따라서 sieve에서는 현재 수 `i`에 새 prime `p`를 붙일 때, `p`가 이미 `i`를 나누는지 여부가 중요합니다.

## Linear Sieve 구현

아래 코드는 `phi`, `mu`, 약수 개수 `tau`를 `O(N)`에 계산합니다.

아래 여러 int 배열을 함께 만들면 N=10^7에서 약 240MB(32비트 int 배열 6개)와 primes 공간이 필요하므로 필요한 함수만 남깁니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <vector>
using namespace std;

struct MultiplicativeSieve {
    vector<int> primes;
    vector<int> isComposite;
    vector<int> phi;
    vector<int> mu;
    vector<int> exponent;
    vector<int> coreTau;
    vector<int> tau;

    explicit MultiplicativeSieve(int limit)
        : isComposite(limit + 1, 0),
          phi(limit + 1, 0),
          mu(limit + 1, 0),
          exponent(limit + 1, 0),
          coreTau(limit + 1, 1),
          tau(limit + 1, 1) {
        if (limit == 0) return;
        phi[1] = 1;
        mu[1] = 1;
        exponent[1] = 0;
        tau[1] = 1;

        for (int i = 2; i <= limit; ++i) {
            if (!isComposite[i]) {
                primes.push_back(i);
                phi[i] = i - 1;
                mu[i] = -1;
                exponent[i] = 1;
                coreTau[i] = 1;
                tau[i] = 2;
            }

            for (int prime : primes) {
                long long value = 1LL * i * prime;
                if (value > limit) {
                    break;
                }

                int next = (int)value;
                isComposite[next] = 1;

                if (i % prime == 0) {
                    phi[next] = phi[i] * prime;
                    mu[next] = 0;
                    exponent[next] = exponent[i] + 1;
                    coreTau[next] = coreTau[i];
                    tau[next] = coreTau[next] * (exponent[next] + 1);
                    break;
                }

                phi[next] = phi[i] * (prime - 1);
                mu[next] = -mu[i];
                exponent[next] = 1;
                coreTau[next] = tau[i];
                tau[next] = tau[i] * 2;
            }
        }
    }
};
```

`tau`는 같은 prime power가 늘어날 때 기존 `(k+1)` factor를 `(k+2)`로 바꿔야 합니다. 그래서 `coreTau`처럼 해당 prime power를 제외한 나머지 부분을 따로 들고 있습니다.

## Dirichlet Convolution과 닫힘

두 multiplicative function의 Dirichlet convolution도 multiplicative입니다.

```text
h = f * g
h(n) = sum_{d|n} f(d)g(n/d)
```

그래서 `phi * 1 = id`, `mu * 1 = epsilon`, `tau = 1 * 1` 같은 관계를 prime power에서 확인한 뒤 전체로 확장할 수 있습니다.

## Summatory Function으로 이어지기

문제가 아래처럼 모든 값을 더하라고 하면 단순 sieve만으로 부족할 수 있습니다.

```text
sum_{i=1..N} phi(i)
sum_{i=1..N} mu(i)
sum_{i=1..N} floor(N / i) * f(i)
```

`N`이 `10^7` 정도면 prefix sum을 만들면 됩니다. `N`이 `10^11` 이상이면 같은 `floor(N/i)` 값을 묶거나 더 고급 summatory technique가 필요합니다.

## 시간 복잡도

| 작업 | 복잡도 |
| --- | ---: |
| linear sieve | `O(N)` |
| simple divisor zeta | `O(N log N)` |
| 각 수 factorization with SPF | 전체 대략 `O(N log N)` |
| prefix sum query | 전처리 후 `O(1)` |

여러 함수를 동시에 구해도 sieve loop는 하나로 묶을 수 있습니다.