1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
int mu[50009], vis[50009], sum[50009], prime[50009], cnt;
void linear_shaker(int N) {
sum[1] = mu[1] = 1;
for (int i = 2; i <= N; ++i) {
if (!vis[i]) {
prime[++cnt] = i;
mu[i] = -1;
}
for (int j = 1; j <= cnt && prime[j] * i <= N; ++j) {
vis[prime[j] * i] = 1;
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
} else mu[i * prime[j]] = -mu[i];
}
sum[i] = sum[i-1] + mu[i];
}
}
int F(int n, int m) {
//Count (n, m) == 1
int ret = 0;
if (n > m) swap(n, m);
for (int i = 1, last; i <= n; i = last + 1) {
last = min(n / (n / i), m / (m / i));
ret += (sum[last] - sum[i - 1]) * (n / i) * (m / i);
}
/*
for (int d = 1; d <= n; ++d)
ret += mu[d] * (n / d) * (m / d);
*/
return ret;
}
int G(int a, int b, int k) {
return F(a / k, b / k);
}
void solve(int a, int b, int c, int d, int k) {
printf("%d\n", G(b, d, k) - G(a-1, d, k) - G(b, c-1, k) + G(a-1, c-1, k));
}
int main() {
linear_shaker(50000);
int a, b, c, d, k, n = getint();
for (int i = 0; i < n; ++i) {
a = getint(); b = getint(); c = getint(); d = getint(); k = getint();
solve(a, b, c, d, k);
}
return 0;
}
|
，然后再枚举除法的商就好了。