洛谷P3455 笔记

传送门

又是一道看了tj的题。

题意

\(t\) 次询问，每次询问给定 \(n\)，\(m\)，\(k\) ，求 \(\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]\)。

\(1\le t\le 5\times10^4\)，\(1\le k\le n\) , \(m\le 5\times10^4\)

正文

把 \(k\) 扔到上界去，记原式变为 \(\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]\)

然后利用莫比乌斯函数性质，把等于 \(1\) 的判断去掉，得 \(\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|gcd(i,j)}\mu(d)\)

接着把 \(d\) 扔到前面去，把整除的条件去掉，记 \(r=min(\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor)\) ，得 \(\sum_{d=1}^{r}\sum_{i=1}^{\lfloor \frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}\mu(d)\)

最后一步很显然，\(\mu(d)\) 放到前面，得到最后的柿子： \(\sum_{d=1}^{r}\mu(d)\lfloor \frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor\)

这个时候思路很显然了。线性筛筛出 \(1\) 到 \(5 \times 10^4\) 内的所有 \(\mu(i)\) 并做一个前缀和，然后就可以整除分块了。

code

//writer:Oier_szc

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,INF=2e9,mod=1e9+7;
int t,n,a,b,d;
int f[N],qzh[N];
int primes[N],st[N],len=0;
void xxs()
{
	f[1]=1;
	for(int i=2;i<=5e4;++i)
	{
		if(!st[i]) primes[++len]=i,f[i]=-1;
		for(int j=1;j<=len&&primes[j]<=5e4/i;++j)
		{
			st[i*primes[j]]=true;
			if(i%primes[j]==0) 
			{
				f[i*primes[j]]=0;
				break;
			}
			else f[i*primes[j]]=-f[i];
		}
	}
	for(int i=1;i<=5e4;++i) qzh[i]=qzh[i-1]+f[i];
}
signed main()
{
	xxs();
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld%lld",&a,&b,&d);
		a/=d,b/=d;
		n=min(a,b);
		int ans=0;
		for(int l=1,r;l<=n;l=r+1)
		{
			r=min(a/(a/l),b/(b/l));
			ans+=(qzh[r]-qzh[l-1])*(a/l)*(b/l);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

总结一下，可以发现这道题推柿子的技巧在于将难以处理的判断条件用一些转换去掉，得到最终柿子后又用到了线性筛和整除分块的技巧以降低复杂度。