lyzqs的博客

推荐一篇题解

里面的思路挺清晰的

没下typora一堆公式打不出来就先咕咕咕好了

学习莫比乌斯反演中

代码：

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 10000050
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
using namespace std;
char In[Max],*ss=In,*tt=In;
namespace lyzqs
{
    il int read()
    {
        char c=getchar();
        int x=0,f=1;
        while(c>'9'||c<'0')
        {
            if(c=='-') f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            x=x*10+c-'0';
            c=getchar();
        }
        return x*f;
    }
    int p[Max],mu[Max],g[Max],n,m;
    ll s[Max],ans,cnt;
    bool vst[Max];
    il void getmu()
    {
        mu[1]=1;
        for(int i=2;i<=Max-1;i++)
        {
            if(!vst[i]) p[++cnt]=i,mu[i]=-1;
            for(int j=1;j<=cnt&&p[j]*i<=Max-1;j++)
            {
                vst[p[j]*i]=1;
                if(i%p[j]==0) break;
                mu[p[j]*i]=-mu[i];
            }
        }
    }
    il void main()
    {
        getmu();
        for(int i=1;i<=cnt;i++)
            for(int j=1;j*p[i]<=Max-1;j++) g[j*p[i]]+=mu[j];
        for(int i=1;i<=Max-1;i++)
            s[i]=s[i-1]+(ll)g[i];
        int T=read();
        while(T--)
        {
            n=read(),m=read();
            if(n>m) swap(n,m);
            ans=0;
            for(int l=1,r;l<=n;l=r+1)
            {
                r=min(n/(n/l),m/(m/l));
                ans+=1ll*(n/l)*(m/l)*(s[r]-s[l-1]);
            }
            printf("%lld\n",ans);
        }
    }
}
int main()
{
    lyzqs::main();
}