OI - YY的GCD(洛谷)

我感觉我懂了莫比乌斯反演（然而没有

---

# 题面

> Linked 洛谷 P2257

点击展开/折叠 题面

设质数集为 $\mathbb P$，给定 $N,M$，求

$$\sum_{x=1}^N\sum_{y=1}^M[\gcd(x,y)\in\mathbb P]$$

---

# 解析

反正都知道是莫比乌斯反演了就直接开始推式子（

$$\begin{aligned} &\sum_{x=1}^N\sum_{y=1}^M[\gcd(x,y)\in\mathbb P]\\ =&\sum_{d\in\mathbb P}\sum_{i=1}^N\sum_{j=1}^M[\gcd(x,y)=d]\\ \end{aligned}$$

发现 $i,j$ 的求和其实就是问 $i\in[1,N],j\in[1,M]$ 中有多少对 $(i,j)$ 的 $\gcd$ 为 $d$，设为 $F(d)$。然后就有一个套路，反演成 $G(d)$ 表示“有多少对 $(i,j)$ 满足 $d\mid\gcd(i,j)$”。

$$G(x)=\sum_{x|d}F(d)\Rightarrow F(x)=\sum_{x|d}G(d)\mu\left(\frac dx\right)$$

而 $G(x)$ 本身很好计算，只要让 $i,j$ 都是 $x$ 的倍数，即 $G(x)=\lfloor\frac Nx\rfloor\lfloor\frac Mx\rfloor$。

继续推式子（不妨设 $N\le M$）：

$$\begin{aligned} &\sum_{d\in\mathbb P}\sum_{d\mid t}\mu\left(\frac td\right)\left\lfloor\frac Nt\right\rfloor\left\lfloor\frac Mt\right\rfloor\\ =&\sum_{t=1}^N\left\lfloor\frac Nt\right\rfloor\left\lfloor\frac Mt\right\rfloor\sum_{d\in\mathbb P\\d\mid t}\mu\left(\frac td\right) \end{aligned}$$

枚举 $t$ 的部分可以用数论分块做到 $O(\sqrt N)$，而枚举 $d$ 的部分是和 $t$ 相关的，设为 $H(t)$。分析 $t$ 和 $H(t)$ 的关系（设 $t$ 的质因子分解能分解出 $c_t$ 个质因子，相同的质因子重复计算）：

若存在 $x\in\mathbb P$ 使得 $x^2\mid y$，则称 $x$ 是 $y$ 的“平方因子”，同理有“立方因子”

1. 若 $t$ 没有平方因子，则 $d$ 相当于枚举了一个质因子，$d$ 有 $c_t$ 个取值，$\frac td$ 含有 $c_t-1$ 个不同质因子，则 $H(t)=\pm c_t$；
2. 若 $t$ 只有一个平方因子且没有立方因子，设 $d’$ 为 $t$ 的平方因子，则只有 $\frac t{d’}$ 没有相同的质因子，则 $H(t)=\pm1$；
3. 否则 $\frac td$ 都有重复质因子，则 $H(t)=0$。

Tab. 上面的 $\pm$ 取决于质因子个数（有奇数个质因子时 $\mu(x)=-1$，否则为 $+1$）。

只要线性筛筛出 $c_t$ 以及所有不含平方因子的数（这些数筛出来后就可以根据情况1直接计算 $H(t)$）；而对于情况2，枚举平方因子是哪个质数，即枚举形式 $ip^2$，其中 $p\not\mid i$，且 $i$ 不含平方因子，再根据情况2计算 $H(t)$。

处理出 $H(t)$ 的前缀和，然后就可以数论分块了。

---

# 源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e7+10,M=1e4;
bool vis[N],tag[N]; //tag 标记是否有平方因子
int prm[N/10],nprm;
int pcnt[N];
long long ans[N]; //H(t)

void Init(){
	for(int i=2;i<N;i++){
		if(!vis[i]){
			prm[++nprm]=i;
			pcnt[i]=1;
		}
		if(!tag[i]) ans[i]=(pcnt[i]&1)? (pcnt[i]):(-pcnt[i]);
		for(int j=1;j<=nprm && 1ll*i*prm[j]<N;j++){
			int k=prm[j]*i;
			vis[k]=true,tag[k]=tag[i],pcnt[k]=pcnt[i]+1;
			if(i%prm[j]==0){tag[k]=true;break;}
		}
	}
	for(int i=1;i<=nprm && 1ll*prm[i]*prm[i]<N;i++){
		int tmp=prm[i]*prm[i];
		for(int j=1;j*tmp<N;j++)
			if(j%prm[i] && !tag[j])
				ans[j*tmp]=(pcnt[j*tmp]&1)? 1:-1;
	}
	for(int i=1;i<N;i++) ans[i]+=ans[i-1];
}
inline int Read(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r;
}
int main(){
	Init();
	int cas=Read();
	while(cas--){
		int n=Read(),m=Read();
		if(n>m) swap(n,m);
		long long tot=0;
		for(int i=1;i<=n;i++){
			int j=min(n/(n/i),m/(m/i));
			tot+=(ans[j]-ans[i-1])*(n/i)*(m/i);
			i=j;
		}
		printf("%lld\n",tot);
	}
	return 0;
}

---

THE END

Thanks for reading!

$$\begin{split} “\ &当\ 万木俱焚\ 别走近我\\ &就让\ 所有的梦境\ 不坠落\ ”\\ ——&\text{《404 Not Found》By 赤羽} \end{split}$$

> Linked 404 Not Found-Bilibili