HDU 1695 GCD（歐拉函數+容斥原理）

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1695

題意：x位于區間[a, b]，y位于區間[c, d]，求滿足GCD(x, y) = k的(x, y)有多少組，不考慮順序。

思路：a = c = 1簡化了問題，原問題可以轉化為在[1, b/k]和[1, d/k]這兩個區間各取一個數，組成的數對是互質的數量，不考慮順序。我們讓d > b，我們枚舉區間[1, d/k]的數i作為二進制組的第二位，因為不考慮順序我們考慮第一位的值時，隻用考慮小于i的情況。對于i<=b，因為第一位[1, i]都可以取到，互質的對數就是歐拉函數值。現在考慮i位于[b/k+1, d/k]，此時我們要用b - [1, b/k]中與i不互質數的個數，那麼關鍵問題就是求[1, b/k]中與i不互質數的個數，我們将i分解質因子，在b/k範圍内每個因子的倍數肯定與i不互質。設i的素因子分别的p1,p2...pk,則1..b/k中p1的倍數組成集合A1,p2的倍數組成集合A2,p3到A3.....pk到Ak,　由于集合中會出現重複的元素，是以用容斥原理來求A1并A2并A3.....并Ak的元素的數的個數。區間中與i不互質的個數 = （區間中i的每個質因數的倍數個數）-（區間中i的每兩個質因數乘積的倍數）+（區間中i的每3個質因數的乘積的倍數個數）-（區間中i的每4個質因數的乘積）+ ...

code：

1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 const int MAXN = 100005;
 7 
 8 LL phi[MAXN];       // 歐拉函數的和
 9 int num[MAXN];      // 素因子個數
10 int p[MAXN][20];    // 素因子
11 
12 void init()
13 {
14     memset(phi, 0, sizeof(phi));
15     memset(num, 0, sizeof(num));
16     phi[1] = 1L;
17     for (int i = 2; i < MAXN; ++i) {
18         if (!phi[i]) {
19             for (int j = i; j < MAXN; j += i) {
20                 if (!phi[j]) phi[j] = j;
21                 phi[j] = phi[j] * (i - 1) / i;
22                 p[j][num[j]++] = i;
23             }
24         }
25         phi[i] += phi[i - 1];
26     }
27 }
28 
29 LL dfs(int idx, int b, int now) // 求不大于b的數中,與now不互質的數的個數;
30 {
31     LL ret = 0;
32     for (int i = idx; i < num[now]; ++i) { // 容斥原理來求A1并A2并A3.....并Ak的元素的數的個數
33         ret += b / p[now][i] - dfs(i + 1, b / p[now][i], now);
34     }
35     return ret;
36 }
37 
38 
39 int main()
40 {
41     init();
42     int nCase;
43     scanf("%d", &nCase);
44     for (int cas = 1; cas <= nCase; ++cas) {
45         int a, b, c, d, k;
46         scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);
47         if (k == 0) {
48             printf("Case %d: 0\n", cas);
49             continue;
50         }
51         if (b > d) swap(b, d);
52         b /= k;
53         d /= k;
54         LL ans  = phi[b];
55         for (int i = b + 1; i <= d; ++i) {
56             ans += b - dfs(0, b, i); // 求不大于b的數中,與i不互質的數的個數
57         }
58         printf("Case %d: %lld\n", cas, ans);
59     }
60     return 0;
61 }      

轉載于:https://www.cnblogs.com/ykzou/p/4781364.html