HDU 1695 (莫比乌斯反演) GCD

题意：

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

分析：

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

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

在最后的例题2中有个重要的结论：

 #include <cstdio>

 #include <algorithm>

 typedef long long LL;

 const int maxn = ;

 int mu[maxn + ], vis[maxn + ], prime[maxn], cnt;

 void Mobius()

 {

     mu[] = ;

     cnt = ;

     for(int i = ; i <= maxn; ++i)

     {

         if(!vis[i])

         {

             mu[i] = -;

             prime[cnt++] = i;

         }

         for(int j = ; j < cnt && i*prime[j] <= maxn; ++j)

         {

             vis[i*prime[j]] = ;

             if(i % prime[j] != ) mu[i*prime[j]] = -mu[i];

             else

             {

                 mu[i*prime[j]] = ;

                 break;

             }

         }

     }

 }

 int main()

 {

     //freopen("1695in.txt", "r", stdin);

     Mobius();

     int T;

     scanf("%d", &T);

     for(int kase = ; kase <= T; ++kase)

     {

         int a, b, c, d, k;

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

         if(k == )

         {

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

             continue;

         }

         b /= k, d /= k;

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

         LL hehe = , haha = ;

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

             hehe += (LL)mu[i] * (b/i) * (d/i);

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

             haha += (LL)mu[i] * (b/i) * (b/i);    //因为题目不区分xy的顺序，所以要减去重复的部分

         LL ans = hehe - haha/;

         printf("Case %d: %I64d\n", kase, ans);

     }

     return ;

 }