「莫比乌斯反演」

Author Avatar
ShioKiri 9月 23, 2019
  • 在其它设备中阅读本文章

Update on A.D.2019-09-23

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

整除分块

公式

求:

对于每个$\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互质的数的数目

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

完全积性函数

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

狄利克雷卷积

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

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

常用的狄利克雷卷积

莫比乌斯函数

线性筛求莫比乌斯函数

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
$

莫比乌斯反演

对于函数

即对于

Problem

P2303 [SDOI2012]Longge的问题

P2257 YY的GCD

原式

原式

设$T=kd$有原式

#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

#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

#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;
}

本文由 ShioKiri 原创,采用 保留署名-非商业性使用-禁止演绎 4.0-国际许可协议
本文链接:https://blog.66ccff.xyz/2019/mobius/