[数据结构与算法]【题解】Luogu P2257 YY的GCD

P2257

$T$ 组数据。

给定 $N,M$ ，求 $1\le x\le N,1\le y\le M$ ,$\text{gcd}(x,y)$ 为质数的对数。

$T\le 10^4,N,M\le 10^7$

Solution

根据题意，其实是求（假设 $n<m$ ）：
$$\sum _{i=1}^n\sum _{j=1}^m[\text{gcd}(i,j)\in Prime]$$
化简式子，先枚举质数：
$$\sum _{p\in Prime}\sum _{i=1}^n\sum _{j=1}^m[\text{gcd}(i,j)==p]$$
同时除以 $p$：
$$\sum _{p\in Prime}\sum _{i=1}^{?\frac{n}{p}?}\sum _{j=1}^{?\frac{m}{p}?}[\text{gcd}(i,j)==1]$$
我们知道 $?(x)=\{\begin{array}{l}1x=1\\ 0\text{otherwise}\end{array}$

而 $?=\mu ?1=\sum _{d|n}\mu (d)$

故$$\sum _{p\in Prime}\sum _{i=1}^{?\frac{n}{p}?}\sum _{j=1}^{?\frac{m}{p}?}\sum _{d|\text{gcd}(i,j)}\mu (d)$$

先枚举 $d$ ：
$$\sum _{p\in Prime}\sum _{d=1}^{?\frac{n}{p}?}\mu (d)??\frac{n}{pd}???\frac{m}{pd}?$$

优化时间复杂度的一个常规操作，令 $k=pd$，枚举 $k$ ：
$$\sum _{k=1}^n\sum _{p\in Prime,p\mid n}\mu (\frac{k}{p})??\frac{n}{k}???\frac{m}{k}?$$

设 $f(n)=\sum _{p\in Prime,p\mid n}\mu (\frac{n}{p})$，考虑预处理

若 $n\in Prime$ ，则 $f(n)=?1$

否则，若 $n$ 最小的质因子是 $r$ ，则

若 $r^2\mid n$ ，当 $\frac{n}{r}$ 没有平方因子时，$f(n)=\mu (\frac{n}{r})$ ， 否则 $f(n)=0=\mu (\frac{n}{r})$

若 $r^2?p$ ，$f(n)=\sum _{p\in Prime,p\mid n}\mu (\frac{n}{p})=\mu (\frac{n}{r})+\sum _{p\in Prime,p\mid \frac{n}{r}}\mu (\frac{n}{pr})\mu (r)$

即 $f(n)=\mu (\frac{n}{r})?\sum _{p\in Prime}\mu (\frac{n}{pr})=\mu (\frac{n}{r})?f(\frac{n}{r})$

在欧拉筛的时候递推计算即可。

其余部分整除分块，时间复杂度 $O(N+\sqrt{N})$

AC Code

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define int long long
using namespace std;

const int SIZE=1e4+5,N=1e7+5;

int T;
int a[SIZE],b[SIZE];
int prime[N],miu[N],v[N],f[N];
int n;

void euler()
{
	int m=0;miu[1]=1;
	for(register int i=2;i<=n;i++)
	{
		if(!v[i]) v[i]=i,miu[i]=-1,f[i]=1,prime[++m]=i;
		for(register int j=1;j<=m;j++)
		{
			if(prime[j]>v[i]||prime[j]*i>n) break;
			v[i*prime[j]]=prime[j];
			miu[i*prime[j]]=(i%prime[j]?-miu[i]:0);
			f[i*prime[j]]=(i%prime[j]?miu[i]-f[i]:miu[i]);
		}
	}
}

signed main()
{
	scanf("%lld",&T);
	for(register int i=1;i<=T;i++)
	{
		scanf("%lld%lld",&a[i],&b[i]);
		if(a[i]>b[i]) swap(a[i],b[i]);
		n=max(n,a[i]);
	}
	euler();    //数据范围较大，离线处理
	for(register int i=2;i<=n;i++) f[i]+=f[i-1];   //前缀和优化
	for(register int i=1;i<=T;i++)
	{
		int ans=0,n=a[i],m=b[i];
		for(register int l=1,r=0;l<=n;l=r+1)    //整除分块
		{
			r=min(n/(n/l),m/(m/l));
			ans+=(f[r]-f[l-1])*(n/l)*(m/l);
		}
		printf("%lld\n",ans);
	}
	return 0;
}