【HDU】1695 GCD

题意：x在[a,b]内，y在[c,d]内，求GCD(x,y)=k的个数，题目保证a=c=1。

由于GCD(x,y)=k，则GCD(x/k,y/k)=1。

那么只要求x在[1,b/k]内，y在[1,d/k]内的互质对数，(x,y)与(y,x)是等价的。

 1 #include<cstdio>
 2 #include<vector>
 3 #define MAXN 100010
 4 typedef long long LL;
 5 using namespace std;
 6 vector<int> fac[MAXN];
 7 void Init() {
 8     int i, j;
 9     for (i = 0; i < MAXN; i++)
10         fac[i].clear();
11     for (i = 2; i < MAXN; i++) {
12         if (fac[i].size())
13             continue;
14         fac[i].push_back(i);
15         for (j = 2; i * j < MAXN; j++)
16             fac[i * j].push_back(i);
17     }
18 }
19 int NoPrime(int x, int &k, int t) {
20     int i, res;
21     res = 1;
22     for (i = k = 0; x; x >>= 1, i++) {
23         if (x & 1) {
24             k++;
25             res *= fac[t][i];
26         }
27     }
28     return res;
29 }
30 int Prime(int x, int m) {
31     int i, j, t, res1, res2, tmp;
32     t = (int) fac[x].size();
33     res1 = res2 = 0;
34     for (i = 1; i < (1 << t); i++) {
35         tmp = NoPrime(i, j, x);
36         if (j & 1) {
37             res1 += m / tmp;
38             res2 += x / tmp;
39         } else {
40             res1 -= m / tmp;
41             res2 -= x / tmp;
42         }
43     }
44     return m - res1 - (x - res2);
45 }
46 int main() {
47     int T, ca = 1;
48     int a, b, c, d, i, k;
49     LL ans;
50     Init();
51     scanf("%d", &T);
52     while (T--) {
53         scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
54         printf("Case %d: ", ca++);
55         if (k == 0 || b < k || d < k)
56             puts("0");
57         else {
58             b /= k, d /= k;
59             if (b > d)
60                 swap(b, d);
61             ans = d;
62             for (i = 2; i <= b; i++)
63                 ans += Prime(i, d);
64             printf("%I64d\n", ans);
65         }
66     }
67     return 0;
68 }