我们可以枚举每一个质数，那么答案就是
$\sum_{p}\sum_{d<=n}\mu(d)*\lfloor n / pd \rfloor *\lfloor m / pd \rfloor$
直接做？TLE
考虑优化，由于看到了pd是成对出现的，令T=pd
$ans=\sum_{T<=min(n,m)}\lfloor n / T \rfloor *\lfloor m / T \rfloor \sum_{p \mid T}\mu(T/p)$
或者
$ans=\sum_{T<=min(n,m)}\lfloor n / T \rfloor *\lfloor m / T \rfloor \sum_{d \mid T}\mu(d)$
显然第一个更好求，我们只需要枚举质数即可
根据欧拉公式近似$\sum_{i=1} \frac{1}{i} = ln n + r$
每个质数均摊logn的复杂度，那么质数个数是n/logn的，我们就可以O(n)预处理了。
如果枚举第二个的话，复杂度是nlogn的
然后算出前缀和，进行下界函数分块即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 10000005
int mu[maxn],pr[maxn],top,sim[maxn];
bool vis[maxn];
void init()
{
memset(vis,false,sizeof vis);
mu[1]=1;
F(i,2,maxn-1)
{
if (!vis[i]) pr[++top]=i,mu[i]=-1;
F(j,1,top)
{
if (pr[j]*i>=maxn) break;
vis[i*pr[j]]=true;
if (i%pr[j]==0) {mu[i*pr[j]]=0;break;}
mu[i*pr[j]]=-mu[i];
}
}
// F(i,1,10) printf("%d ",mu[i]);
} int t,n,m; ll solve(int n,int m)
{
ll ret=0;
if (n>m) swap(n,m);
for (int i=1,last=0;i<=n;i=last+1)
{
last=min(n/(n/i),m/(m/i));
ret+=((ll)sim[last]-sim[i-1])*(m/i)*(n/i);
}
return ret;
} int main()
{
init();
F(i,1,top)
F(j,1,inf)
{
if (pr[i]*j>=maxn) break;
sim[pr[i]*j]+=mu[j];
}
F(i,1,maxn-1) sim[i]+=sim[i-1];
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
printf("%lld\n",solve(n,m));
}
}
然后我们发现这个函数是可以线性筛的，尽管它不是积性函数
$g(pr[j]*i)=\mu (i) ,pr[j] \mid i$
$g(pr[j]*i)=\mu(i)-g[i] , pr[j] \nmid i$
然后就可以$\Theta (n)$去预处理了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 10000005
int mu[maxn],pr[maxn],top,sim[maxn];
bool vis[maxn];
void init(int tmp)
{
memset(vis,false,sizeof vis);
mu[1]=1;sim[1]=0;
F(i,2,tmp)
{
if (!vis[i])
{
pr[++top]=i;
mu[i]=-1;
sim[i]=1;
}
F(j,1,top)
{
if (pr[j]*i>tmp) break;
vis[i*pr[j]]=true;
if (i%pr[j]==0)
{
mu[i*pr[j]]=0;
sim[i*pr[j]]=mu[i];
break;
}
mu[i*pr[j]]=-mu[i];
sim[i*pr[j]]=mu[i]-sim[i];
}
}
F(i,1,tmp) sim[i]+=sim[i-1];
} int t; ll solve(int n,int m)
{
ll ret=0;
for (int i=1,last=0;i<=n;i=last+1)
{
last=min(n/(n/i),m/(m/i));
ret+=((ll)sim[last]-sim[i-1])*(m/i)*(n/i);
}
return ret;
} int n[10005],m[10005]; int main()
{
F(i,1,maxn-1) sim[i]+=sim[i-1];
scanf("%d",&t);int tmp=0;
F(i,1,t)
{
scanf("%d%d",&n[i],&m[i]);
if (n[i]>m[i]) swap(n[i],m[i]);
tmp=max(tmp,n[i]);
}
init(tmp);
F(i,1,t)printf("%lld\n",solve(n[i],m[i]));
}