G37 狄利克雷卷积

G38 和式的变换

G39 莫比乌斯反演

问题

给出 $n,m,k$（$1 \leq n,m,k \leq 10^5$），求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m \lbrack \gcd(i,j)=k \rbrack$

即：满足 $1 \leq i \leq n$，$1 \leq j \leq m$，且 $\gcd(i,j)=k$ 的二元组 $(i,j)$ 的数量。

题解

到此，在 $\sum\limits_{d=1}^n$ 中 $\mu(d)$ 可以前缀和， $\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d}\rfloor$ 可以分块加速即可，从而避免了 $d$ 逐个枚举 $1 \dots n$。

具体代码如下：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5e4;
int pr, p[N+10];LL mu[N+10]; bool v[N+10];
void init()
{
	memset(v,0,sizeof(v));
	pr=0;mu[0]=0;mu[1]=1;
    for(int i=2;i<=N;i++)
	{
        if(!v[i]) p[++pr]=i, mu[i]=-1; 
        for(int j=1;j<=pr&&p[j]*i<=N;j++)
		{
            v[i*p[j]]=true;
            if(i%p[j]==0){mu[i*p[j]]=0;break;}
            mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1;i<=N;i++) mu[i]+=mu[i-1];
}
LL calc(int n, int m)
{
    if(n>m)swap(n,m);
	LL ans=0;
    for(int l=1,r;l<=n;l=r+1)
	{
        r=min(n/(n/l), m/(m/l));
        ans+=(mu[r]-mu[l-1])*(n/l)*(m/l);
    }
    return ans;
}
int main()
{
	init();
	int T,n,m,k;scanf("%d",&T);
	while(T--)
	{
        scanf("%d%d%d",&n,&m,&k);
		n/=k;m/=k; 
        printf("%lld\n",calc(n,m));
	}
    return 0;
}