那些年，你望尘莫及的“莫比乌斯反演”

ACM算法日常

发布于 2021-07-16 16:07:37

7740

发布于 2021-07-16 16:07:37

文章被收录于专栏：ACM算法日常ACM算法日常

但凡是接触过算法竞赛的，一定或多或少的听到过“莫比乌斯反演”的大名，这个高大上的名字下面究竟是什么精深的数论知识，我来带你揭晓。

笔者

笔者曾获得 ICPC 2020 世界总决赛资格，ICPC 2020 亚洲区域总决赛第五名。

本次内容

本次内容主要围绕莫比乌斯反演展开，主要内容如下：

数论函数
- 积性函数
Dirichlet 卷积
莫比乌斯函数
莫比乌斯反演
- 反演的基本形式
- 经典例题

数论函数

定义域为正整数的函数称为数论函数。

积性函数

如果

\forall a,b, (a,b)=1,f(ab)=f(a)f(b)

这样的数论函数称为积性函数。

常见的数论函数：

完全积性函数

如果

\forall a,b,f(ab)=f(a)f(b)

这样的数论函数称为完全积性函数。

常见的完全积性函数有：

f(x)=e^x

f(x)=x

Dirichlet 卷积

莫比乌斯函数

莫比乌斯反演

经典例题1

https://www.lydsy.com/JudgeOnline/problem.php?id=2301

【HAOI2011】Problem b

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const LL p_max = 100010;
LL mu[p_max];
void get_mu() {
    mu[1] = 1;
    static bool vis[p_max];
    static LL prime[p_max], p_sz, d;
    for (int i=2;i<p_max;i++)
    {
        if (!vis[i]) {
            prime[p_sz++] = i;
            mu[i] = -1;
        }
        for (LL j = 0; j < p_sz && (d = i * prime[j]) < p_max; ++j) {
            vis[d] = 1;
            if (i % prime[j] == 0) {
                mu[d] = 0;
                break;
            }
            else mu[d] = -mu[i];
        }
    }
}

LL T,a,b,n,m,k,f[p_max];

LL calc(LL n,LL m)
{
    if(n>m) swap(n,m);
    LL ans=0;
    for (LL i=1;i<=n/k;)
    {
        LL p=n/i/k,q=m/i/k;
        p=min(n/k,n/p/k),q=min(n/k,m/q/k);
        p=min(p,q);
        ans+=(f[p]-f[i-1])*(n/i/k)*(m/i/k);
        i=p+1;
    }
    return ans;
}

void init()
{
    f[0]=0;
    for (int i=1;i<p_max;i++)
        f[i]=f[i-1]+mu[i];
}

int main()
{
    get_mu();init();
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld%lld%lld%lld",&a,&n,&b,&m,&k);
        printf("%lld\n",calc(n,m)-calc(a-1,m)-calc(n,b-1)+calc(a-1,b-1));
    }
    return 0;
}

经典例题2

https://www.spoj.com/problems/LCMSUM/

【SPOJ】LCM Sum

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const LL p_max = 1000100;
LL phi[p_max];
void get_phi() {
    phi[1] = 1;
    static bool vis[p_max];
    static LL prime[p_max], p_sz, d;
    for (int i=2;i<p_max;i++){
        if (!vis[i]) {
            prime[p_sz++] = i;
            phi[i] = i - 1;
        }
        for (LL j = 0; j < p_sz && (d = i * prime[j]) < p_max; ++j) {
            vis[d] = 1;
            if (i % prime[j] == 0) {
                phi[d] = phi[i] * prime[j];
                break;
            }
            else phi[d] = phi[i] * (prime[j] - 1);
        }
    }
}

LL T,n,f[p_max],g[p_max];

int main()
{
    get_phi();
    for (int i=1;i<p_max;i++)
        f[i]=phi[i]*i;
    memset(g,0,sizeof(g));
    for (int i=2;i<p_max;i++)
        for (int j=i;j<p_max;j+=i)
            g[j]+=f[i];
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld",&n);
        printf("%lld\n",g[n]*n/2LL+n);
    }
    return 0;
}

经典例题3

http://acm.hdu.edu.cn/showproblem.php?pid=4944

【hdu4944】 FSF’s game

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const LL p_max = 500100;
LL phi[p_max];
void get_phi() {
    phi[1] = 1;
    static bool vis[p_max];
    static LL prime[p_max], p_sz, d;
    for (int i=2;i<p_max;i++){
        if (!vis[i]) {
            prime[p_sz++] = i;
            phi[i] = i - 1;
        }
        for (LL j = 0; j < p_sz && (d = i * prime[j]) < p_max; ++j) {
            vis[d] = 1;
            if (i % prime[j] == 0) {
                phi[d] = phi[i] * prime[j];
                break;
            }
            else phi[d] = phi[i] * (prime[j] - 1);
        }
    }
}

LL T,n,f[p_max],g[p_max],sum[p_max];

int main()
{
    get_phi();
    for (int i=1;i<p_max;i++)
        f[i]=phi[i]*i;
    memset(g,0,sizeof(g));
    for (int i=2;i<p_max;i++)
        for (int j=i;j<p_max;j+=i)
            g[j]+=f[i];
    for (int i=1;i<p_max;i++)
        f[i]=g[i]*i/2LL+i;
    f[0]=0;
    for (int i=1;i<p_max;i++)
        f[i]+=f[i-1];
    for (LL d=1;d<p_max;d++)
    {
        for (LL i=1;i*d<p_max;i++)
        {
            sum[d*i]+=d*d*f[i];
            if (d*(i+1)<p_max) sum[d*(i+1)]-=d*d*f[i];
        }
    }
    sum[0]=0;
    for (int i=1;i<p_max;i++)
        sum[i]+=sum[i-1];
    scanf("%lld",&T);int cass=0;
    while(T--)
    {
        scanf("%lld",&n);
        printf("Case #%d: %u\n",++cass,(unsigned)sum[n]);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-06-19，如有侵权请联系 cloudcommunity@tencent.com 删除

https