洛谷 P2257 YY的GCD（莫比乌斯反演）

Description:

神犇YY虐完数论后给傻×kAc出了一题

给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对

kAc这种傻×必然不会了，于是向你来请教……

多组输入

Input:

第一行一个整数T 表述数据组数

接下来T行，每行两个正整数，表示N, M

T = 10000

N, M <= 10000000

Output

T行，每行一个整数表示第i组数据的结果

Sample Input:

2
10 10
100 100

Sample Output:

30
2791

题目链接

题意为求出 $T$T 组 ${\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)\in prime]$i=1∑n​j=1∑m​[gcd(i,j)∈prime]

首先我们令 $n\&lt;m$n<m ，之后对此式进行化简，将 $gcd(i,j)$gcd(i,j) 设为变量 $p$p 得

$\sum _{p=1}^n\sum _{i=1}^n\sum _{j=1}^m\left[gcd\right(i,j)=p](p\in prime)$p=1∑n​i=1∑n​j=1∑m​[gcd(i,j)=p](p∈prime)

化简得

$\sum _{p=1}^n\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{p}\rfloor }\left[gcd\right(i,j)=1]$p=1∑n​i=1∑⌊pn​⌋​j=1∑⌊pm​⌋​[gcd(i,j)=1]

利用莫比乌斯函数性质可得

$\sum _{p=1}^n\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{p}\rfloor }\sum _{d\mid gcd(i,j)}\mu \left(d\right)$p=1∑n​i=1∑⌊pn​⌋​j=1∑⌊pm​⌋​d∣gcd(i,j)∑​μ(d)

考虑枚举 $d$d 得

$\sum _{p=1}^n\sum _{d=1}^{\lfloor \frac{n}{p}\rfloor }\mu \left(d\right)\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }\left[d\mid i\right]\sum _{j=1}^{\lfloor \frac{m}{p}\rfloor }\left[d\mid j\right]$p=1∑n​d=1∑⌊pn​⌋​μ(d)i=1∑⌊pn​⌋​[d∣i]j=1∑⌊pm​⌋​[d∣j]​

其中 ${\sum }_{i=1}^{\lfloor \frac{n}{p}\rfloor }\left[d\mid i\right]$i=1∑⌊pn​⌋​[d∣i] 为 $[1,\lfloor \frac{n}{p}\rfloor ]$[1,⌊pn​⌋] 中 $d$d 的倍数， ${\sum }_{j=1}^{\lfloor \frac{m}{p}\rfloor }\left[d\mid j\right]$j=1∑⌊pm​⌋​[d∣j] 为 $[1,\lfloor \frac{m}{p}\rfloor ]$[1,⌊pm​⌋] 中 $d$d 的倍数，两项可化简为 $\lfloor \frac{n}{pd}\rfloor$⌊pdn​⌋ 与 $\lfloor \frac{m}{pd}\rfloor$⌊pdm​⌋

这样可以推导出 ${\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)\in prime]={\sum }_{d=1}^{\lfloor \frac{n}{p}\rfloor }\mu \left(d\right)\lfloor \frac{n}{pd}\rfloor \lfloor \frac{m}{pd}\rfloor (p\in prime,n\&lt;m)$i=1∑n​j=1∑m​[gcd(i,j)∈prime]=d=1∑⌊pn​⌋​μ(d)⌊pdn​⌋⌊pdm​⌋(p∈prime,n<m)

其中莫比乌斯函数 $\mu$μ 可以用线性筛筛出，但是这样 $O\left(n\right)$O(n) 枚举 $d$d 的计算复杂度在多组输入中还不是正确的复杂度

考虑继续化简该式，令 $T=pd$T=pd ，代入得

$\sum _{T=1}^n\sum _{p\mid T}\mu \left(\frac{T}{p}\right)\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor$T=1∑n​p∣T∑​μ(pT​)⌊Tn​⌋⌊Tm​⌋

整理得

$\sum _{T=1}^n\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor \sum _{p\mid T}\mu \left(\frac{T}{p}\right)$T=1∑n​⌊Tn​⌋⌊Tm​⌋p∣T∑​μ(pT​)

发现其中 ${\sum }_{p\mid T}\mu \left(\frac{T}{p}\right)$p∣T∑​μ(pT​) 部分可以做前缀和预处理，另外 $\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor$⌊Tn​⌋⌊Tm​⌋ 部分使用分块优化就可以愉(jian)快(nan)地 $AC$AC 掉这道题目啦

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = (int)(1e7 + 5);

bool IsPrime[maxn];
int Tot;
int Prime[maxn];
int Mu[maxn];
long long F[maxn];
long long Prefix[maxn];

void Moblus() {
	for (int i = 0; i < maxn; ++i) IsPrime[i] = true;
	Mu[1] = 1;
	for (int i = 2; i < maxn; ++i) {
		if (IsPrime[i]) {
			Prime[Tot++] = i;
			Mu[i] = -1;
		}
		for (int j = 0; j < Tot && Prime[j] * i < maxn; ++j) {
			IsPrime[i * Prime[j]] = false;
			if (i % Prime[j] == 0) {
				Mu[i * Prime[j]] = 0;
				break;
			}
			Mu[i * Prime[j]] = -Mu[i];
		}
	}
	for (int i = 0; i < Tot; ++i) {
		for (int j = 1; Prime[i] * j < maxn; ++j) {
			F[j * Prime[i]] += Mu[j];
		}
	}
	for (int i = 1; i < maxn; ++i) Prefix[i] = Prefix[i - 1] + F[i];
}

long long Solve(int N, int M) {
	if (N > M) swap(N, M);
	long long Res = 0;
	for (int t = 1, tp; t <= N; t = tp + 1) {
		tp = min(N / (N / t), M / (M / t));
		Res += (Prefix[tp] - Prefix[t - 1]) * (N / t) * (M / t);
	}
	return Res;
}

int T;
int N, M;

int main(int argc, char *argv[]) {
	Moblus();
	scanf("%d", &T);
	for (int Case = 1; Case <= T; ++Case) {
		scanf("%d%d", &N, &M);
		printf("%lld\n", Solve(N, M));
	}
	return 0;
}