积性函数

若函数$f:N\to R$，满足对于任意一对互质的正整数$p,q(\gcd(p,q)=1)$，都有$f(pq)=f(p)f(q)$，则称$f$为积性函数。
根据积性函数的定义，$f(x)$可以表示成下面的形式

$$f(p_1^{k_1}p_2^{k_2}p_3^{k_3}...p_{n}^{k_n})=f(p_1^{k_1})f(p_2^{k_2})f(p_3^{k_3})...f(p_{n}^{k_n})$$

积性函数的求法：欧拉筛。

void Euler(int n) {
    f[1] = 1;
    //calc_f(x, p)快速计算，f(x^p)
    for (int i = 2; i <= n; ++i) {
        if (!flag[i])prime[++*prime] = i, f[i] = calc_f(i, 1);
        for (int j = 1; j <= *prime; ++j) {
            int to = i * prime[j];
            if (to > n)break;
            flag[to] = true;
            if (i % prime[j] == 0) {
                cnt[to] = cnt[i] + 1;//prime[j]是i最小的素因子，此时i已经有prime[j]因子，所以这里需要将素因子为prime[j]的这一项去掉，把次数+1乘回来
                f[to] = f[i] / calc_f(prime[j], cnt[i]) * calc_f(prime[j], cnt[to]);
                break;
            }
            //如果prime[j]不是i的素因子，也就是说to相比i增加了一个素因子，所以直接乘上f(prime[j])
            cnt[to] = 1;
            f[to] = f[i] * calc_f(prime[j], 1);
        }
    }
}

常见积性函数：

$$\begin{align} 1(n)&=1\\ id(n)&=n\\ \epsilon(n)&=[n=1]\\ \phi(n)&=\sum\limits_{i=1}^n[\gcd(n,i)=1]\\ d(n)&=\sum\limits_{i=1}^n[i|n] \end{align}$$

莫比乌斯反演

已知$g(n)$的因数和$f(n)=\sum\limits_{d|n}g(d)$，通过$f$反求$g$。

$$g(n)=\sum\limits_{d|n}\mu(\dfrac{n}{d})f(d)$$

其中$\mu$称为莫比乌斯函数，定义为

$$\mu(n)=\begin{cases} 1&n=1\\ (-1)^k&n=p_1p_2p_3...p_k\\ 0&其他 \end{cases}=\begin{cases} (-1)^k&n无平方因子\\ 0&n有平方因子 \end{cases}$$

那么我们有莫比乌斯反演定理1

$$f(n)=\sum\limits_{d|n}g(d)\Leftrightarrow g(n)=\sum\limits_{d|n}\mu(\dfrac{n}{d})f(d)$$

若存在正整数$N$使得$\forall n\in N,f(n)=g(n)=0$，则有莫比乌斯反演定理2

$$f(n)=\sum\limits_{n|m,m\le N}g(m)\Leftrightarrow g(n)=\sum\limits_{n|m,m\le N}\mu(\dfrac{m}{n})f(m)$$

TIPS:$\sum\limits_{d|d’}d\mu(\dfrac{d’}{d})=\phi(d’)$

狄利克雷卷积

设$f:N\to R,g:N\to R$是两个函数，则它们的狄利克雷卷积为

$$(f*g)(n)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d})$$

命题：若$f(n),g(n)$是积性函数，则$h(n)=(f*g)(n)$也是积性函数。
定理：$f=g*1\Leftrightarrow g=f*\mu$
狄利克雷卷积符合交换律、结合律。
一些公式

$$\begin{align} \epsilon&=\mu*1\\ id&=\phi*1\\ \phi&=\mu*id \end{align}$$

杜教筛

快速求积性函数的前缀和，时间复杂度$O(n^{\frac{2}{3}})$。
定义梅滕斯函数$M(n)=\sum\limits_{i=1}^n\mu(n)$，可得

$$M(n)=1-\sum\limits_{i=2}^nM(\lfloor\dfrac{n}{i}\rfloor)$$

用整除分块加速后面的求和，时间复杂度为$O(n^{\frac{3}{4}})$，预处理前$O(n^{\frac{2}{3}})$的数据，则可以将复杂度降到$O(n^{\frac{2}{3}})$。

ll sumM(ll n) {
    if (n <= lim)return smu[n];
    if (M.count(n))return M[n];
    ll ans = 1;
    for (ll l = 2, r; l <= n; l = r + 1) {
        ll d = n / l;
        r = n / d;
        ans = del(ans, mul(sumM(d), (r - l + 1) % mod));
    }
    return M[n] = ans;
}