[bzoj 2820] YY的GCD

求1≤x≤N, 1≤y≤M且gcd(x,y)为质数的(x,y)的数目, T组数据. (T = 10000, N,M≤10^7) 弱化版: [bzoj 2818] Gcd

本题多组数据且x,y范围不同.

然后就不会捉了QAQ 数某范围内互质的数对可以做到, 但是这里还得枚举一下素数.

看了一下Po姐的PPT. 肯定得预处理点什么东西. 这里在莫比乌斯函数一项做手脚. 令, 把对它求和剥离出来:

线性筛打莫比乌斯函数表, 用筛法预处理, 再求个前缀和. 利用除法取整的分段性即可做到回答.

学到了另一种方法. 设. 令. 当, 含素数的平方, 仅当时被加数可能非0. 当, ; 注意这里的比中的多一个, 而那一项等于.

综合以上, 有

在黄学长博文的评论下看到有人提到这种方法. 可以参考BZOJ 2820: YY的GCD [莫比乌斯反演]【学习笔记】 - Candy? - 博客园

typedef long long ll;
const int N = 1e7;
short mu[N + 1];
ll sum[N + 1];

void sieve()
{
	static bool f[N + 1];
	static int prime[N/10];
	int cnt = 0;
	mu[1] = 1;
	For (i, 2, N) {
		if (!f[i]) {
			prime[cnt++] = i;
			mu[i] = -1;
		}
		for (int j = 0, t; j < cnt && (t = prime[j] * i) <= N; ++j) {
			f[t] = true;
			if (i % prime[j]) mu[t] = -mu[i];
			else break;
		}
	}
	Rep (i, 0, cnt)
		for (int j = 1, t; (t = j * prime[i]) <= N; ++j)
		sum[t] += mu[j];
	For (i, 2, N) sum[i] += sum[i-1];
}

inline ll solve(int n, int m)
{
	ll ans = 0;
	for (int i = 2, ed = min(m, n), j; i <= ed; i = j+1) {
		int _n = n/i, _m = m/i;
		j = min(ed, min(n/_n, m/_m));
		ans += (sum[j] - sum[i-1]) * _n * _m;
	}
	return ans;
}

int main()
{
	sieve();
	int T;
	scanf("%d", &T);
	while (T--) {
		int n, m;
		scanf("%d%d", &n, &m);
		printf("%lld\n", solve(n, m));
	}
	return 0;
}

方法二, 跑得快一些.

void sieve()
{
	static bool f[N + 1];
	static int prime[N/10];
	int cnt = 0;
	mu[1] = 1;
	For (i, 2, N) {
		if (!f[i]) {
			prime[cnt++] = i;
			mu[i] = -1;
			sum[i] = 1;
		}
		for (int j = 0, t; j < cnt && (t = prime[j] * i) <= N; ++j) {
			f[t] = true;
			if (i % prime[j]) {
				mu[t] = -mu[i];
				sum[t] = mu[i] - sum[i];
			} else {
				sum[t] = mu[i];
				break;
			}
		}
		sum[i] += sum[i-1];
	}
}