题目链接：

题意：x位于区间[a, b]，y位于区间[c, d]，求满足GCD(x, y) = k的(x, y)有多少组，不考虑顺序。

思路：

其中u(p)为莫比乌斯函数，运用上面的公式可以快速求出结果，但是不考虑顺序，还要减去重复算的那一部分。让b<d，那么重复的一部分只可能在前面的区间出现，减去前面的一半即可。

code：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 typedef long long LL; 6 const int MAXN = 100005; 7  8 bool check[MAXN]; 9 int prime[MAXN];10 int mu[MAXN];11 12 void moblus()13 {14     memset(check, false, sizeof(check));15     mu[1] = 1;16     int tot = 0;17     for (int i = 2; i < MAXN; ++i) {18         if (!check[i]) {19             prime[tot++] = i;20             mu[i] = -1;21         }22         for (int j = 0; j < tot; ++j) {23             if (i * prime[j] > MAXN) break;24             check[i * prime[j]] = true;25             if (i % prime[j] == 0) {26                 mu[i * prime[j]] = 0;27                 break;28             } else {29                 mu[i * prime[j]] = -mu[i];30             }31         }32     }33 }34 35 int main()36 {37     moblus();38     int nCase;39     scanf("%d", &nCase);40     for (int cas = 1; cas <= nCase; ++cas) {41         int a, b, c, d, k;42         scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);43         if (k == 0) {44             printf("Case %d: 0\n", cas);45             continue;46         }47         b /= k;48         d /= k;49         if (b > d) swap(b, d);50         LL ans = 0;51         for (int i = 1; i <= b; ++i)52             ans += (LL)mu[i] * (b / i) * (d / i);53         LL tmp = 0;54         for (int i = 1; i <= b; ++i)55             tmp += (LL)mu[i] * (b / i) * (b / i);56         ans -= tmp / 2;57         printf("Case %d: %lld\n", cas, ans);58     }59     return 0;60 }