题目链接
https://www.luogu.com.cn/problem/P3455
题解
经典的莫比乌斯反演题。
题目要求的是：
$$\sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=d]$$
不妨先设 \(a \leq b\)。
首先除一个 \(d\)：
$$\sum_{i=1}^{\left \lfloor \frac{a}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{b}{d} \right \rfloor} [\gcd(i,j)=1]$$
然后根据莫比乌斯函数的性质换元：
$$\sum_{i=1}^{\left \lfloor \frac{a}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{b}{d} \right \rfloor} \sum_{x|\gcd(i,j)}\mu(x)$$
有这样一个性质：若 \(x|\gcd(i,j)\)，则 \(x|i\) 且 \(x|j\)。所以我们继续：
$$\sum_{i=1}^{\left \lfloor \frac{a}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{b}{d} \right \rfloor} \sum_{x|i,x|j}\mu(x)$$
枚举 \(x\)：
$$\sum_{i=1}^{\left \lfloor \frac{a}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{b}{d} \right \rfloor} \sum_{x=1}^{a}\mu(x)[x|i][x|j]$$
交换求和顺序：
$$\sum_{x=1}^a \mu(x) \sum_{i=1}^{\left \lfloor \frac{a}{d} \right \rfloor} [x|i] \sum_{j=1}^{\left \lfloor \frac{b}{d} \right \rfloor} [x|j]$$
然后继续换元：
$$\sum_{x=1}^{a}\mu(x)\left \lfloor \frac{a}{dx} \right \rfloor\left \lfloor \frac{b}{dx} \right \rfloor$$
这个式子就可以直接算了。
然而直接算的时间复杂度是 \(O(a)\) 的，所以我们需要用整除分块优化一下，从而将时间复杂度优化到 \(O(\sqrt a)\)。
#include <iostream>
#include <algorithm>
#define N 50000
using namespace std;
int mu[50005],vis[50005],pri[50005];
void init()
{
int cnt=0;
mu[1]=vis[1]=1;
for(int i=2;i<=N;i++)
{
if(!vis[i])
mu[i]=-1,pri[++cnt]=i;
for(long long j=1;j<=cnt&&pri[j]*i<=N;j++)
{
int x=pri[j]*i;
vis[x]=1;
if(i%pri[j]==0)
{
mu[x]=0;
break;
}
else
mu[x]=-mu[i];
}
}
for(int i=1;i<=N;i++)
mu[i]+=mu[i-1];
}
int main()
{
int t;
cin>>t;
init();
while(t--)
{
int n,m,d;
long long ans=0;
cin>>n>>m>>d;
if(n>m)swap(n,m);
n/=d,m/=d;
for(int l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans+=(long long)(mu[r]-mu[l-1])*(n/l)*(m/l);
}
cout<<ans<<endl;
}
return 0;
}