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：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 LL phi[MAXN];       // 欧拉函数的和

 int num[MAXN];      // 素因子个数

 int p[MAXN][];    // 素因子

 void init()

 {

     memset(phi, , sizeof(phi));

     memset(num, , sizeof(num));

     phi[] = 1L;

     for (int i = ; i < MAXN; ++i) {

         if (!phi[i]) {

             for (int j = i; j < MAXN; j += i) {

                 if (!phi[j]) phi[j] = j;

                 phi[j] = phi[j] * (i - ) / i;

                 p[j][num[j]++] = i;

             }

         }

         phi[i] += phi[i - ];

     }

 }

 LL dfs(int idx, int b, int now) // 求不大于b的数中,与now不互质的数的个数;

 {

     LL ret = ;

     for (int i = idx; i < num[now]; ++i) { // 容斥原理来求A1并A2并A3.....并Ak的元素的数的个数

         ret += b / p[now][i] - dfs(i + , b / p[now][i], now);

     }

     return ret;

 }

 int main()

 {

     init();

     int nCase;

     scanf("%d", &nCase);

     for (int cas = ; cas <= nCase; ++cas) {

         int a, b, c, d, k;

         scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);

         if (k == ) {

             printf("Case %d: 0\n", cas);

             continue;

         }

         if (b > d) swap(b, d);

         b /= k;

         d /= k;

         LL ans  = phi[b];

         for (int i = b + ; i <= d; ++i) {

             ans += b - dfs(, b, i); // 求不大于b的数中,与i不互质的数的个数

         }

         printf("Case %d: %lld\n", cas, ans);

     }

     return ;

 }

巴特西

HDU 1695 GCD（欧拉函数+容斥原理）

最新文章

热门文章