bzoj 1101[POI2007]Zap-莫比乌斯反演

题意：T组数据，每组给出m，n，d 求 ∑ni=1∑nj=1[gcd(i,j)==d](T≤50000,n,m,d<=50000)

Solution:

首先大家要记住一些结论：

μ∗1=[n==1]
类似地，
φ∗1=n

这些结论是莫比乌斯反演的精髓

然后我们就开始化简式子（一定要克服公式恐惧症啊QwQ）

N=nd,M=md

ans=∑ni=1∑nj=1[gcd(i,j)==d]

=∑Ni=1∑Mj=1[gcd(i,j)==1] （这一步大家自己yy一下吧）

=∑Ni=1∑Mj=1∑d|gcd(i,j)μ(d)（μ∗1=[n==1]）

=∑Ni=1∑Mj=1∑d|i∑d|jμ(d)

=∑min(N,M)d=1μ(d)∑Ni=1∑d|i∑Mj=1∑d|j1 (转变成主动枚举d)

=∑min(N,M)d=1μ(d)⌊Nd⌋⌊Md⌋ (观察后面的式子可以发现实际上就是枚举d的倍数)

然后我们就得到了单次 O(n) 的做法，但是依然过不了这个题，我们需要优化：我们发现，对于多个连续的d， ⌊Nd⌋⌊Md⌋ 的值是一样的，所以我们可以把μ改成前缀和的形式，就可以达成 O(n√) 的复杂度了，具体实现就一行：

last=min(n/(n/i),m/(m/i))

这里是利用了C++默认下取整的性质，具体为什么大家可以思考一下

代码：

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,T,d;
bool vis[50010];
int prim[50010];
int cnt,miu[50010],sum[50010];
int get_miu(int n)
{
    miu[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!vis[i]) prim[++cnt]=i,miu[i]=-1;
        for (int j=1;j<=cnt&&i*prim[j]<=n;j++)
        {
            vis[i*prim[j]]=1;
            miu[i*prim[j]]=-miu[i];
            if (i%prim[j]==0) {miu[i*prim[j]]=0;break;}
        }
    }
    for (int i=1;i<=n;i++)
        sum[i]=sum[i-1]+miu[i];
}
int main()
{
    get_miu(50000);
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&n,&m,&d);
        int last=0;
        int ans=0;
        n/=d,m/=d; for (int i=1;i<=min(n,m);i=last+1) { last=min(n/(n/i),m/(m/i));
            ans+=(sum[last]-sum[i-1])*(n/i)*(m/i);
        }
        printf("%d\n",ans);
    }
}