Description

　　FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a
，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。
Input

　　第一行包含一个正整数n，表示一共有n组询问。（1<=n<= 50000）接下来n行，每行表示一个询问，每行三个
正整数，分别为a,b,d。（1<=d<=a,b<=50000）
Output

　　对于每组询问，输出到输出文件zap.out一个正整数，表示满足条件的整数对数。
Sample Input
2

4 5 2

6 4 3
Sample Output
3

2

//对于第一组询问，满足条件的整数对有(2,2)，（2,4），（4，2）。对于第二组询问，满足条件的整数对有（

6,3），（3,3）。

解题方法： 莫比乌斯反演。
先普及一下莫比乌斯反演，
莫比乌斯反演
贾志鹏线性筛

解题方法来自博主Regina8023的描述。
如果直接枚举d来做会TLE，但是我们发现a’/d的值在d等于好多值得时候都是相同的。

比如a’=100,那么d在[34,50]之间a’/d都是2。

那么我们可以把连续的一段d一起来算（分块）：

设a’/d=x，那么最后一个a’/d=x的d=a’/x，所以这段连续的区间就是[d,a’/(a’/d)]

结合b’/d，取个min就可以了。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 50005;
typedef long long LL;
int tot, mu[maxn], pri[maxn];
int sum[maxn];
bool mark[maxn];
void getMobius(){
    mu[1] = 1;
    tot = 0;
    memset(mark, 0, sizeof(mark));
    for(int i = 2; i <= 50000; i++){
        if(!mark[i]) pri[++tot] = i, mu[i] = -1;
        for(int j = 1; j <= tot && i * pri[j] <= 50000; j++){
            mark[i*pri[j]] = 1;
            if(i % pri[j] == 0){
                mu[i*pri[j]] = 0;
                break;
            }
            else mu[i*pri[j]] = -mu[i];
        }
    }
    sum[0] = 0LL;
    for(int i = 1; i <= 50000; i++) sum[i] = sum[i-1] + mu[i];
}

int main(){
    getMobius();
    int T;
    scanf("%d", &T);
    while(T--){
        int a, b, D;
        scanf("%d%d%d", &a, &b, &D);
        a /= D, b /= D;
        int x = min(a, b), pos;
        int ans = 0LL;
        for(int d = 1; d <= x; d = pos+1){
            pos = min(a / (a / d), b / (b / d));
            ans += (sum[pos] - sum[d - 1]) * (a / d) * (b / d);
        }
        printf("%d\n", ans);
    }
    return 0;
}