2301: [HAOI2011]Problem b

Time Limit: 50 Sec Memory Limit: 256 MB

Submit: 3757 Solved: 1671

[Submit][Status][Discuss]

Description

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

Input

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

Output

共n行，每行一个整数表示满足要求的数对(x,y)的个数

Sample Input

2

2 5 1 5 1

1 5 1 5 2

Sample Output

14

3

题解

此题是一道莫比乌斯反演的例题，看了好久题解。自己好笨啊！

解法同是莫比乌斯反演+分块，莫比乌斯反演就不说了，分块就是一段区间内，不同的$ (n / i)$ 只有$ \sqrt n $ 个，于是就分块了，单次询问复杂度只有 $O (\sqrt n + \sqrt m) $.

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int N = 5e4 + 10;

int mu[N], s[N], prime[N];

void init() {

	memset(s, 1, sizeof s);

	mu[1] = 1; int i, j, totp = 0; long long t;

	for (i = 2; i < N; ++i) {

		if (s[i]) mu[i] = -1, prime[totp++] = i;

		for (j = 0; j < totp; ++j) {

			t = (long long)i * prime[j];

			if (t > N) break;

			s[t] = 0;

			if (i % prime[j]) mu[t] = -mu[i];

			else mu[t] = 0, j = totp;

		}

	}

	s[0] = 0;

	for (i = 1; i < N; ++i) s[i] = s[i - 1] + mu[i];

}

long long Cal(int n, int m) {

	if (n > m) swap(n, m);

	long long ret = 0;

	for (int i = 1, j; i <= n; i = j + 1) {

		j = min(n / (n / i), m / (m / i));

		ret += (long long)(s[j] - s[i - 1]) * (n / i) * (m / i);

	}

	return ret;

}

int main() {

	init();

	int a, b, c, d, k, T;

	long long t;

	scanf("%d", &T);

	while (T--) {

		scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);

		--a, --c; a /= k; b /= k; c /= k; d /= k;

		t = Cal(b, d) + Cal(a, c);

		t -= Cal(a, d) + Cal(b, c);

		printf("%lld\n", t);

	}

	return 0;

}