[HDOJ1695]GCD

　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695

　　两个区间内各取一个数，使这两个数的gcd为确定值，统计符合条件的数的对数。（认为(a,b)和(b,a)是同一对）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <algorithm>
 6 #include <cmath>
 7 
 8 using namespace std;
 9 
10 typedef long long LL;
11 const int maxn = 100010;
12 
13 LL a, b, c, d, k;
14 vector<LL> fac[maxn];
15 int vis[maxn];
16 
17 inline LL min(LL &a, LL &b) {
18     return a > b ? b : a;
19 }
20 
21 inline void swap(LL &a, LL &b) {
22     a = a ^ b;
23     b = a ^ b;
24     a = a ^ b;
25 }
26 
27 void init() {
28     memset(vis, 0, sizeof(vis));
29     for(int i = 0; i < maxn; i++) {
30         fac[i].clear();
31     }
32     for(int i = 2; i < maxn; i+=2) {
33         fac[i].push_back(2);
34     }
35     for(int i = 3; i < maxn; i+=2) {
36         if(!vis[i]) {
37             for(int j = i; j < maxn; j+=i) {
38                 vis[j] = 1;
39                 fac[j].push_back(i);
40             }
41         }
42     }
43 }
44 
45 LL inc(int j, int w) {
46     int cnt = 0;
47     LL m = 1;
48     for(int i = 0; i < fac[w]. size(); i++) {
49         if(j & (1 << i)) {
50             cnt++;
51             m *= fac[w][i];
52         }
53     }
54     int sum = k / m;
55     if(cnt % 2 == 1) {
56         return sum;
57     }
58     else {
59         return -sum;
60     }
61 }
62 
63 LL solve() {
64     LL ans = 0;
65     b /= k; 
66     d /= k;
67     if(b > d) {
68         swap(b, d);
69     }
70     for(int i = 1; i <= d; i++) {
71         k = min((LL)i, (LL)b);
72         ans += k;
73         int nn = 1 << fac[i].size();
74         for(int j = 1; j < nn; j++) {
75             ans -= inc(j, i);
76         }
77     }
78     return ans;
79 }
80 
81 int main() {
82     init();
83     int T;
84     scanf("%d", &T);
85     for(int i = 1; i <= T; i++) {
86         scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);
87         if(k == 0) {
88             printf("Case %d: 0\n", i);
89             continue;
90         }
91         LL ans = solve();
92         printf("Case %d: %I64d\n", i, ans);
93     }
94     return 0;
95 }