莫比乌斯反演入门题
(Description)
神犇GJS虐完数论后给zzHGR出了一个数论题。
给定n,m,求1≤x≤n,1≤y≤m且gcd(x,y)为质数的(x,y)有多少对。
zzHGR必然不会了，于是向你来请教……
多组输入。
(Input)
第一行一个整数T，表述数据组数。
接下来T行，每行两个正整数，表示n,m。
(Output)
T行，每行一个整数表示第i组数据的结果
(Sample Input)
2
10 10
100 100
(Sample Output)
30
2791
(HINT)
T=10000
n,m≤107
这道题是莫比乌斯反演入门题，对于刚接触莫比乌斯反演的萌新很友好，如果没有了解过莫比乌斯反演的点这里
可以发现这道题最后求的式子就是$$sum_{k=1}nsum_{i=1}nsum_{j=1}^m[gcd(i,j)=k](kin prime)$，于是我们就直接开始推式子了。
$$sum_{k=1}nsum_{i=1}nsum_{j=1}^m[gcd(i,j)=k](kin prime)$$
我们看到([gcd(i,j)=k])，就会有一种将(k)改成(1)的冲动，于是我们冲动的将(k)除掉
$$=sum_{k=1}nsum_{i=1}{leftlfloorfrac{n}{k}
ight
floor}sum_{j=1}^{leftlfloorfrac{m}{k}
ight
floor}[gcd(i,j)=1]$$
接着，莫比乌斯函数的性质又出现了：(sum_{dmid n}mu(d)=[n=1])，这个东西特别有用，可以帮助我们把(gcd[i,j]=1)消掉，于是我们考虑将(n)替换成([gcd(i,j)=1])，得到
$$=sum_{k=1}nsum_{i=1}{leftlfloorfrac{n}{k}
ight
floor}sum_{j=1}^{leftlfloorfrac{m}{k}
ight
floor}sum_{dmid gcd(i,j)}mu(d)$$
此时我们可以看到多出现了一个(d)，于是我们考虑将(d)提前枚举，因为(dmid gcd(i,j)且i<= leftlfloorfrac{n}{k}
ight
floor，j<=leftlfloorfrac{m}{k}
ight
floor)，所以(d<=min(leftlfloorfrac{n}{k}
ight
floor,leftlfloorfrac{m}{k}
ight
floor))，我们假设(n<=m)，则有(d<=leftlfloorfrac{n}{k}
ight
floor)，而此时枚举出来的(d)并不一定满足(dmid gcd(i,j))，所以最后我们还要加一个判断
$$=sum_{k=1}nsum_{d=1}{leftlfloorfrac{n}{k}
ight
floor}mu(d)sum_{i=1}{leftlfloorfrac{n}{k}
ight
floor}sum_{j=1}{leftlfloorfrac{m}{k}
ight
floor}[dmid gcd(i,j)]$$
这时我们发现后面那个([dmid gcd(i,j)])又长又臭，于是我们发现只要(d)满足([dmid i] 且 [dmid j])，就一定满足([dmid gcd(i,j)])
$$=sum_{k=1}nsum_{d=1}{leftlfloorfrac{n}{k}
ight
floor}mu(d)sum_{i=1}^{leftlfloorfrac{n}{k}
ight
floor}[dmid i]sum_{j=1}^{leftlfloorfrac{m}{k}
ight
floor}[dmid j]$$
我们发现式子里的(sum_{i=1}^{leftlfloorfrac{n}{k}
ight
floor}[dmid i]sum_{j=1}^{leftlfloorfrac{m}{k}
ight
floor}[dmid j])还是很丑，于是我们考虑对于一个满足普遍性的式子(sum_{i=1}^n[xmid i])，它的本质就是求满足(kx<=n)中(k)的个数，可以轻易得到(k=frac{n}{x})，于是我们可以把(sum_{i=1}^{leftlfloorfrac{n}{k}
ight
floor}[dmid i]sum_{j=1}^{leftlfloorfrac{m}{k}
ight
floor}[dmid j])化为(frac{leftlfloorfrac{n}{k}
ight
floor}{d}frac{leftlfloorfrac{m}{k}
ight
floor}{d}= leftlfloorfrac{n}{kd}
ight
floorleftlfloorfrac{m}{kd}
ight
floor)
$$=sum_{k=1}nsum_{d=1}{leftlfloorfrac{n}{k}
ight
floor}mu(d)leftlfloorfrac{n}{kd}
ight
floorleftlfloorfrac{m}{kd}
ight
floor$$
我们发现其中(kd)出现了两次，很烦，于是设(T=kd)，则有
$$=sum_{k=1}nsum_{d=1}{leftlfloorfrac{n}{k}
ight
floor}mu(d)leftlfloorfrac{n}{T}
ight
floorleftlfloorfrac{m}{T}
ight
floor$$
我们考虑枚举(T,k)，因为(T=kd)，所以确定了(T,k)，就确定了(d)
$$=sum_{T=1}^nleftlfloorfrac{n}{T}
ight
floorleftlfloorfrac{m}{T}
ight
floorsum_{kmid T,kin prime}mu(frac{T}{k})$$
这个就是最终的式子，我们考虑对于(sum_{kmid T,kin prime}mu(frac{T}{k}))进行线性筛预处理(O(n))预处理出前缀和，而对于前面的部分我们用整除分块(O(sqrt n))询问，所以最后的复杂度是(O(sqrt n))
代码
#include<bits/stdc++.h>
using namespace std;
const int N=10000010;
int n,m;
int cnt=0;
int prime[N];
int sum[N];
int f[N];
int mu[N];
bool vis[N];
void init()
{
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&&prime[j]*i<=N;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
mu[prime[j]*i]=-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];
}
long long ans=0;
void solve(int a,int b)
{
for(int l=1,r=0;l<=a;l=r+1)
{
r=min(a/(a/l),b/(b/l));
ans+=(long long)(sum[r]-sum[l-1])*(long long)(a/l)*(long long)(b/l);
}
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--)
{
ans=0ll;
scanf("%d %d",&n,&m);
if(n>m)swap(n,m);
solve(n,m);
printf("%lld
",ans);
}
return 0;
}
/*
2
10 10
100 100
*/