「莫比乌斯反演」 | 落影汐雾的x号虚空印刷站

Update on A.D.2019-09-23

参考资料：
莫比乌斯反演-让我们从基础开始
莫比乌斯反演_cnblogs_peng-ym
P2257 YY的GCD 题解
容斥原理 与 莫比乌斯反演
整除分块_peng-ym
OI生涯中的各种数论算法的证明

整除分块

公式

求：

$$\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$$

对于每个$\lfloor\frac{n}{i}\rfloor$值相同的区间$[l,r]$有$r=n/(n/l)$，即对于$\forall x\in [i,n/(n/i)]$有$x=\lfloor\frac{n}{i}\rfloor$.

时间复杂度

$O(\sqrt{n})$

代码

for(int l = 1, r; l <= n; l = r + 1)
{
    r = n / (n / l);
    ans += (r - l + 1) * (n / l);
}

数论函数

满足$f(ab)=f(a)f(b),gcd(a,b)=1$的数论函数称为积性函数
满足$f(ab)=f(a)f(b)$的数论函数称为完全积性函数

积性函数

$\varphi(n)$：欧拉函数，表示小于n的正整数中与n互质的数的数目

$$\varphi(x)=x\prod_{i=1}^{n}\left(1-\frac{1}{p_i}\right)$$

$\mu(n)$：莫比乌斯函数
$\sigma(n)$：因子和函数，表示n的正因子和
$d(n)​$：因子个数函数，表示n的正因数个数

完全积性函数

$\epsilon(n)=[n=1]$：单位函数
$id(n)=n$：恒等函数
$1(n)=1$：常函数

狄利克雷卷积

对于数论函数$f(n),g(n)$定义Dirichlet卷积为

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

若$f,g$为积性函数，$f*g,f\times g$为积性函数

常用的狄利克雷卷积

$$id=\varphi\times 1\quad n=\sum_{d\mid n}\varphi(d)$$ $$\epsilon = \mu \times 1 \quad \epsilon(n) = \sum_{d\mid n}\mu(d)$$ $$\varphi = \mu \times id \quad \varphi(n)=\sum_{d\mid n}d\mu(\frac{n}{d})=\sum_{d\mid n}\mu(d)\frac{n}{d}$$

莫比乌斯函数

$$\mu(d) = \left\{\begin{matrix}1,d=1 \\ (-1)^n,d=\prod_{i=1}^{n}p_i^{k_i} , \forall p_i, k_i=1 \\ 0,d=\prod_{i=1}^{n}p_i^{k_i} , \exists p_i, k_i\geqslant 2 \end{matrix}\right.$$

线性筛求莫比乌斯函数

void sieve()
{
    mu[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++cnt] = i, mu[i] = -1;
        for(int j = 1; j <= cnt && i * prime[j] <= N; j++) {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
    }
}

性质

由
$
\mu \times 1 = \epsilon
$
得

$$\sum_{d|n}\mu(d)=[n=1]$$

莫比乌斯反演

对于函数

$$f=g\times 1$$

有

$$g=\mu \times f$$

即对于

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

有

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

Problem

P2303 [SDOI2012]Longge的问题

$$\sum_{i=1}^{n}gcd(i,n)\\ =\sum_{d\mid n}d\times\sum_{i=1}^{n}[gcd(i,n)=d]\\ =\sum_{d \mid n}d \times \sum_{i=1}^{\frac{n}{d}}[gcd\left ( i,\frac{n}{d}\right)=1]\\ =\sum_{d \mid n} d \cdot \varphi\left ( \frac{n}{d} \right )$$

P2257 YY的GCD

原式

$$=\sum_{k=1}^{min(n,m)}\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k](k\in prime)$$

由

$$\sum_{d|n}\mu(d)=[n=1]$$

得

$$\sum_{d|gcd(i,j)}\mu(d)=[gcd(i,j)=1]$$

原式

$$=\sum_{k=1}^{min(n,m)}\sum_{i=1}^{\lfloor{\frac{n}{k}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{k}}\rfloor}\sum_{d|gcd(i,j)}\mu(d)(k\in prime)$$ $$=\sum_{k=1}^{min(n,m)}\sum_{d=1}^{\lfloor{\frac{n}{k}}\rfloor}\mu(d){\lfloor{\frac{n}{kd}}\rfloor}{\lfloor{\frac{m}{kd}}\rfloor})(k\in prime)$$

设$T=kd$有原式

$$=\sum_{k=1}^{min(n,m)}\sum_{d=1}^{\lfloor{\frac{n}{k}}\rfloor}\mu(d){\lfloor{\frac{n}{T}}\rfloor}{\lfloor{\frac{m}{T}}\rfloor}(k\in prime)$$ $$=\sum_{T=1}^{min(n,m)}{\lfloor{\frac{n}{T}}\rfloor}{\lfloor{\frac{m}{T}}\rfloor}\sum_{k|T,k\in prime}\mu(\frac{T}{k})$$

#include <iostream>
#include <cstdio>

using namespace std;
const int _ = 10000005, N = 10000000;
int T, n, m, cnt;
int vis[_], prime[_], mu[_], f[_], sum[_];
void sieve()
{
    mu[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++cnt] = i, mu[i] = -1;
        for(int j = 1; j <= cnt && i * prime[j] <= N; j++) {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i <= cnt; i++)
        for(int j = 1; prime[i] * j <= N; j++)
            f[j * prime[i]] += mu[j];
    for(int i = 1; i <= N; i++)
        sum[i] = sum[i - 1] + f[i];
}
int main()
{
    sieve();
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        if(n > m) swap(n, m);
        long long ans = 0;
        for(int l = 1, r = 0; l <= n; l = r + 1) {
            r = min(n / (n / l), m / (m / l));
            ans += 1LL * (n / l) * (m / l) * (sum[r] - sum[l - 1]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

P3455 [POI2007]ZAP-Queries

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

#include <iostream>
#include <cstdio>

using namespace std;
const int _ = 50005, N = 50000;
int T, n, m, d;
int vis[_], prime[_], mu[_], sum[_], cnt;
void sieve()
{
    mu[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++cnt] = i, mu[i] = -1;
        for(int j = 1; j <= cnt && i * prime[j] <= N; j++) {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i <= N; i++) sum[i] = sum[i - 1] + mu[i];
}
int main()
{
    sieve();
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &n, &m, &d);
        if(n > m) swap(n, m);
        n /= d; m /= d;
        long long ans = 0;
        for(int l = 1, r = 0; l <= n; l = r + 1) {
            r = min(n / (n / l), m / (m / l));
            ans += 1LL * (n / l) * (m / l) * (sum[r] - sum[l - 1]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

P2522 [HAOI2011]Problem b

$$\sum_{i=a}^b\sum_{j=c}^d[gcd(i,j)=k]$$ $$=\sum_{i=1}^b\sum_{j=1}^d[gcd(i,j)=k]-\sum_{i=1}^{a-1}\sum_{j=1}^d[gcd(i,j)=k]-\sum_{i=1}^b\sum_{j=1}^{c-1}[gcd(i,j)=k]+\sum_{i=1}^{a-1}\sum_{j=1}^{c-1}[gcd(i,j)=k]$$ $$\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=k]$$ $$=\sum_{i=1}^{\lfloor{\frac{n}{k}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{k}}\rfloor}[gcd(i,j)=1]$$ $$=\sum_{i=1}^{\lfloor{\frac{n}{k}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{k}}\rfloor}\sum_{d\mid gcd(i,j)} \mu(d)$$ $$=\sum_{d=1}^{min(n,m)}\mu(d)\lfloor{\frac{n}{d}}\rfloor\lfloor{\frac{m}{d}}\rfloor$$

#include <iostream>
#include <cstdio>

using namespace std;
const int _ = 50005, N = 50000;
int T, a, b, c, d, k;
int vis[_], prime[_], mu[_], sum[_], cnt;
void sieve()
{
    mu[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++cnt] = i, mu[i] = -1;
        for(int j = 1; j <= cnt && i * prime[j] <= N; j++) {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i <= N; i++) sum[i] = sum[i - 1] + mu[i];
}
long long calc(int n, int m, int k)
{
    long long ans = 0;
    n = n / k; m = m / k;
    for(int l = 1, r = 0; l <= min(n, m); l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += 1LL * (n / l) * (m / l) * (sum[r] - sum[l - 1]);
    }
    return ans;
}
int main()
{
    sieve();
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
        long long ans = calc(b, d, k) - calc(a - 1, d, k) - calc(b, c - 1, k) + calc(a - 1, c - 1, k);
        printf("%lld\n", ans);
    }
    return 0;
}

本文由 落影汐雾 原创，采用 保留署名-非商业性使用-禁止演绎 4.0-国际许可协议
本文链接：https://x.lyxw.xyz/2019/mobius/