好题集(9) - LG P2257 YY的GCD

题目传送门。

题意：\(T\) 组询问，每次询问给定 \(n,m\)，求 \(\sum\limits_{x=1}^n\sum\limits_{y=1}^m[\gcd(x,y)\in\mathbb{P}]\)。\(T\le 10^4,n,m\le 10^7\)。

首先我们有引理：\([n=1]=\sum\limits_{d\mid n}\mu(d)\)

我知道这是莫比乌斯函数的基本性质，但我太菜了还是得证一下。

分讨。

当 \(n=1\) 时，显然成立。下面讨论 \(n>1\) 的情况，此时左式为 \(0\)。

考虑 \(n\) 的质因数分解 \(\prod\limits_{i=1}^{\omega(n)} p_i^{\alpha(i)}\)，设集合 \(S=\{p_1,p_2,\cdots,p_{\omega(n)}\}\)。那么 \(n\) 的一个无平方因子的因子 \(d\) 即为 \(S\) 的某一子集 \(X\) 中的数相乘的积。由 \(\mu\) 的定义，有 \(\mu(d)=(-1)^{|X|}\)。

不难发现当 \(|X|=k\) 时，有 \(C_{\omega(n)}^k\) 个不同的 \(|X|\)，每个 \(X\) 对右式的贡献相同。也就是说，我们有：

\[\begin{align*} \sum\limits_{d\mid n}\mu(d)&=\sum\limits_{X\subseteq S}(-1)^{|X|}\\ &=\sum\limits_{k=1}^{\omega(n)}C_{\omega(n)}^k\cdot(-1)^k \tag{1} \end{align*} \]

再来看二项式定理的定义式：

\[(a+b)^v=\sum\limits_{i=0}^v C_v^ia^ib^{v-i} \tag{2} \]

注意到当 \((2)\) 右式中 \(a=1,b=-1,v=\omega(n)\) 时恰好得到 \((1)\) 的右式。容易发现此时 \((2)\) 左式为 \(0\)，也即 \(\sum\limits_{d\mid n}\mu(d)=0\)。

综上，引理得证。

那么利用引理，来推一下式子：

\[\begin{align*} \sum\limits_{x=1}^n\sum\limits_{y=1}^m[\gcd(x,y)\in\mathbb{P}]&=\sum\limits_{p\in\mathbb{P}}\sum\limits_{x=1}^n\sum\limits_{y=1}^m[\gcd(x,y)=p]\\ &=\sum\limits_{p\in\mathbb{P}}\sum\limits_{x=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{y=1}^{\lfloor\frac{m}{p}\rfloor}[\gcd(x,y)=1]\\ &=\sum\limits_{p\in\mathbb{P}}\sum\limits_{x=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{y=1}^{\lfloor\frac{m}{p}\rfloor}\sum\limits_{d\mid\gcd(x,y)}\mu(d)\\ &=\sum\limits_{p\in\mathbb{P}}\sum\limits_{x=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{y=1}^{\lfloor\frac{m}{p}\rfloor}\sum\limits_{d\mid x,d\mid y}\mu(d)\\ &=\sum\limits_{p\in\mathbb{P}}\sum\limits_{d=1}^{\min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)\sum\limits_{x=1,d\mid n}1\sum\limits_{y=1,d\mid m}1\\ &=\sum\limits_{p\in\mathbb{P}}\sum\limits_{d=1}^{\min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)\lfloor\frac{\lfloor\frac{n}{p}\rfloor}{d}\rfloor\lfloor\frac{\lfloor\frac{m}{p}\rfloor}{d}\rfloor\\ &=\sum\limits_{p\in\mathbb{P}}\sum\limits_{d=1}^{\min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor\\ &=\sum\limits_{t=1}^{\min(n,m)}\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\sum\limits_{p\in\mathbb{P},p\mid t}\mu(\frac{t}{p}) \end{align*} \]

发现最后面那坨有点丑，我们设：

\[g(n)=\sum\limits_{p\in\mathbb{P},p\mid n}\mu(\frac{n}{p}) \]

那么我们的式子变为：

\[\sum\limits_{x=1}^n\sum\limits_{y=1}^m[\gcd(x,y)\in\mathbb{P}]=\sum\limits_{t=1}^{\min(n,m)}\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor g(t) \]

先看前面的 \(\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\)。由整除性质知，\(\lfloor\frac{n}{t}\rfloor\) 和 \(\lfloor\frac{m}{t}\rfloor\) 都至多存在 \(O(\sqrt{n})\) 种取值；二者相乘后，由于存在很多重复部分（画数轴即可发现），取值数仍为 \(O(\sqrt{n})\)。因此我们使用数论分块，整段整段地统计前半部分的贡献。

然后看后面的 \(g\)。式子不能再拆开，因此考虑如何整段整段地和前半部分一起统计。

想到用线性筛求出所有 \(\max_n\) 以内的质数，筛法过程中预处理 \(\mu\) 的值。然后对于质数 \(p\)，枚举 \(k\cdot p\le \max_n\)，统计这个 \(p\) 对 \(g(k\cdot p)\) 的贡献即可。

求出所有的 \(g\) 之后，做一遍前缀和，于是可以做到每段 \(O(1)\) 统计。因此我们单次询问的复杂度是 \(O(\sqrt{n})\)

预处理时我们枚举了质数的倍数，所以预处理复杂度是 \(O(n\log n\log n)\) 的。

代码：

#include<iostream>
#define ll long long
using namespace std;

const int N=1e7+5;

int T;
int n,m;

namespace Math{
	
	int tot;
	
	int pri[N],mu[N];
	bool flg[N];
	ll s_g[N],g[N];
	
	inline void init(int n){
		mu[1]=1;
		for(int i=2;i<=n;++i){
			if(!flg[i])pri[++tot]=i,mu[i]=-1;
			for(int j=1;j<=tot&&i*pri[j]<=n;++j){
				flg[i*pri[j]]=1;
				if(!(i%pri[j])){mu[i*pri[j]]=0;break ;}
				mu[i*pri[j]]=-mu[i];
			}
		}
		for(int i=1;i<=tot;++i)for(int j=1;j*pri[i]<=n;++j)g[j*pri[i]]+=mu[j];
		for(int i=1;i<=n;++i)s_g[i]=s_g[i-1]+(1LL*g[i]);
		return ;
	}
	
	inline ll qry_s_g(int l,int r){
		return s_g[r]-s_g[l-1];
	}
	
}using namespace Math;

inline void work(){
	cin>>n>>m;int mn=min(n,m);
	ll res=0;
	int l=1,r=0;
	for(l=1;r<=mn&&l<=mn;l=r+1){//枚举颜色段的左端点
		r=min(n/(n/l),m/(m/l));
		ll val=(1LL*(n/l))*(1LL*(m/l));//这一段内的值
		res+=qry_s_g(l,r)*val;
	}
	return cout<<res<<"\n",void();
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	init(1e7);
	cin>>T;while(T--)work();
	return 0;
}

提交记录。