BZOJ1101 [POI2007]Zap

 1 /**************************************************************
 2     Problem: 1101
 3     User: rausen
 4     Language: C++
 5     Result: Accepted
 6     Time:6208 ms
 7     Memory:1440 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 #include <algorithm>
12  
13 using namespace std;
14 const int N = 50005;
15  
16 int tot;
17 int u[N], sum[N], p[N];
18 bool Flag[N];
19  
20 inline int read() {
21     int x = 0;
22     char ch = getchar();
23     while (ch < ‘0‘ || ‘9‘ < ch)
24         ch = getchar();
25     while (‘0‘ <= ch && ch <= ‘9‘) {
26         x = x * 10 + ch - ‘0‘;
27         ch = getchar();
28     }
29     return x;
30 }
31  
32 void work(int M) {
33     u[1] = 1;
34     int i, j;
35     for (i = 2; i <= M; ++i) {
36         if (!Flag[i])
37             p[++tot] = i, u[i] = -1;
38         for (j = 1; i * p[j] <= M; ++j) {
39             Flag[i * p[j]] = 1;
40             if (i % p[j] == 0) {
41                 u[i * p[j]] = 0;
42                 break;
43             }
44             u[i * p[j]] = -u[i];
45         }
46     }
47     for (i = 1; i <= M; ++i)
48         sum[i] = sum[i - 1] + u[i];
49 }
50  
51 inline int calc(int n, int m) {
52     if (n > m) swap(n, m);
53     int res = 0, pos, i;
54     for (i = 1; i <= n; i = pos + 1) {
55         pos = min(n / (n / i), m / (m / i));
56         res += (sum[pos] - sum[i - 1]) * (n / i) * (m / i);
57     }
58     return res;
59 }
60  
61 int main() {
62     work(50000);
63     int T = read(), a, b, d;
64     while (T--) {
65         a = read(), b = read(), d = read();
66         printf("%d\n", calc(a / d, b / d));
67     }
68     return 0;
69 }