题解 P1390 【公约数的和】

· · 题解

一个莫比乌斯反演的入门题却没有入门的讲解...

莫比乌斯函数

首先介绍一个东西叫做狄利克雷卷积 (后面会用到)

(如果知道下面的结论就不用看了)

我们新定义一个符号(定义新运算) *

定义 $h=f*g$ : $$ h=f*g=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}d)g(d)h=f*g=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}d)g(d) $$ 再定义几个函数 1. $\sum$ 函数 (这里只是一个函数名字而已) 有 对于任意x 有$\sum$ (x)=1 2. $1(x)$ 对于任意x 有$1(x)$ =$x

  1. 单位元 e

    有 e(n)=[n=1] (这个式子的意思是当n=1时 值为1 否则为0)

这个单位元有一个性质 :f*e=e

乘法有逆元 狄利克雷卷积也有逆元

逆元: 如果对于f存在

f*g=e

那么就称g为f的逆元

开始介绍莫比乌斯反演

首先介绍一个东西 叫做莫比乌斯函数 \mu

定义\sum 函数的逆元为 \mu

\mu * \sum= e

写成普通的形式

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

带入之后发现\mu 的取值

\mu(n) = \begin{cases}1,n=1\\0,存在一个平方数是n的因子\\(-1)^m,m是n的质因子个数\end{cases}

从上面我们得到了一个重要的结论1:

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

先求这个式子

\sum_{i<=n} \sum_{d|i} \mu(d)

先枚举了 i, 再考虑 i所有的约数

等价于 先枚举d 在考虑d在范围内所有的倍数

所以它等于

\sum_{d<=n} \lfloor \frac{n}{d} \rfloor \mu(d)

这个作为结论2

求这个式子

\sum_{i<=n} \sum_{j<=m} [(i,j)=1]

用结论1

\sum_{i<=n} \sum_{j<=m} \sum_{d|(i,j)} \mu(d) \sum_{i<=n} \sum_{j<=m} \sum_{d|i} \sum_{d|j} \mu(d) \sum_{i<=n} \sum_{d|i} \sum_{j<=m} \sum_{d|j} \mu(d)

用结论2

\sum_{i<=n} \sum_{d|i}\sum_{d<=m} \lfloor \frac{m}{d} \rfloor \mu(d) \sum_{d<=n}\lfloor \frac{n}{d} \rfloor\sum_{d<=m} \lfloor \frac{m}{d} \rfloor \mu(d) \sum_{d<=min(n,m)} \mu(d)\lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor

这个作为结论3

开始看这道题

(a,b) 表示a和b的最大公约数

我们先求

\sum_{i<=n} \sum_{j<=n} (i,j)

之后开始变化形式:

\sum_{d<=n}d\times \sum_{i<=n} \sum_{j<=n} [(i,j)=d] \sum_{d<=n}d\times \sum_{i<=\lfloor \frac{n}{d}\rfloor} \sum_{j<=\lfloor \frac{n}{d}\rfloor} [(i,j)=1]

令t=n/d

用结论3

求得

\sum_{d<=n}d \times \sum_{d'<=t}\mu(d')\lfloor \frac{t}{d'}\rfloor^2

之后用除法分块即和前缀和即可(不会除法分块可以去康一康余数求和那道题)

这个结果比最终答案多算了一些 减去即可

#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define res register int
#define int unsigned long long
using namespace std;
const int N=2000000+10;
int n; 
int v[N],p[N];
long long mu[N];
long long sum[N];
void prime()
{
    int cnt=0; mu[1]=1;
    for(res i=2;i<=n;i++)
    {
        if(!v[i])
        {
            v[i]=i; p[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt;j++)//保证枚举的是最小质因子 
        {
            if(p[j]>v[i]||i*p[j]>n) break;
            v[i*p[j]]=p[j];
            mu[i*p[j]]=(i%p[j])?-mu[i]:0;
        }
    }
    for(res i=1;i<=n;i++)
        sum[i]=sum[i-1]+mu[i];
}

int calc(int n,int d)
{
    n=n/d; int ret=0,r=0;
    for(res l=1;l<=n;l=r+1)
    {
        int tmp=n/l;
        r=min(n,n/tmp);
        ret+=(sum[r]-sum[l-1])*tmp*tmp;
    }
    return ret;
}

int ans=0;
signed main()
{
    scanf("%d",&n);
    prime();
    for(res d=1;d<=n;d++)
    {
        ans+=d*calc(n,d);
    }
    ans-=n*(n+1)/2;
    ans/=2;
    cout<<ans<<endl;
}