首页 > 代码库 > HDU 1695 (莫比乌斯反演) GCD

HDU 1695 (莫比乌斯反演) GCD

2024-08-09 00:02:22   217人阅读

题意：

从区间[1, b]和[1, d]中分别选一个x, y，使得gcd(x, y) = k, 求满足条件的xy的对数(不区分xy的顺序)

分析：

虽然之前写过一个莫比乌斯反演的总结，可遇到这道题还是不知道怎么应用。

这里有关于莫比乌斯反演的知识，而且最后的例题中就有这道题并给出了公式的推导。

技术分享
 1 #include <cstdio> 2 #include <algorithm> 3 typedef long long LL; 4  5 const int maxn = 1000000; 6 int mu[maxn + 10], vis[maxn + 10], prime[maxn], cnt; 7  8 void Mobius() 9 {10     mu[1] = 1;11     cnt = 0;12     for(int i = 2; i <= maxn; ++i)13     {14         if(!vis[i])15         {16             mu[i] = -1;17             prime[cnt++] = i;18         }19         for(int j = 0; j < cnt && i*prime[j] <= maxn; ++j)20         {21             vis[i*prime[j]] = 1;22             if(i % prime[j] != 0) mu[i*prime[j]] = -mu[i];23             else24             {25                 mu[i*prime[j]] = 0;26                 break;27             }28         }29     }30 }31 32 int main()33 {34     //freopen("1695in.txt", "r", stdin);35     36     Mobius();37     int T;38     scanf("%d", &T);39     for(int kase = 1; kase <= T; ++kase)40     {41         int a, b, c, d, k;42         scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);43         44         if(k == 0)45         {46             printf("Case %d: 0\n", kase);47             continue;48         }49         50         b /= k, d /= k;51         if(b > d) std::swap(b, d);52         LL hehe = 0, haha = 0;53         for(int i = 1; i <= b; ++i)54             hehe += (LL)mu[i] * (b/i) * (d/i);55         for(int i = 1; i <= b; ++i)56             haha += (LL)mu[i] * (b/i) * (b/i);    //因为题目不区分xy的顺序，所以要减去重复的部分57         LL ans = hehe - haha/2;58         59         printf("Case %d: %I64d\n", kase, ans);60     }61     62     return 0;63 }
View Code

 

HDU 1695 (莫比乌斯反演) GCD


联系
我们