题目链接：https://www.acwing.com/problem/content/217/

很棒的题解：https://www.acwing.com/solution/content/63012/

大意是给出abd，求存在多少x<=a,y<=b使得gcd(a,b)=d。

问题可以转化为存在多少gcd(a/d,b/d)=1。

问题可以满足容斥定理，容斥的符号正好是莫比乌斯的符号。

但是效率并不理想，可以达到n^2。因为存在a'/i在区间上存在整除情况，因此可以分块处理，这样我们总能进行一步预处理，O（1）的得到某一个块中的值。

总体复杂度可以达到n/^n。比较郁闷的是容斥的部分还是需要再好好康康。

code：

const int nn = 5e4+10;
int miu[nn];
int v[nn];
int s[nn];
void mobi(int n){
	//miu[i] = 0,存在相等的质因子(即存在平方因子);
	//= 1，所有质因子各不相等且质因子数量为偶数; 
	//= -1，所有质因子各不相同且质因子数量为奇数。
	for(int i=1;i<=n;i++) miu[i] = 1,v[i] = 0;
	for(int i=2;i<=n;i++){
		if(v[i]) continue;
		miu[i] = -1;
		for(int j=2*i;j<=n;j+=i){
			v[j] = 1;
			if((j/i)%i==0) miu[j] = 0;
			else miu[j]*=-1;
		}
	}
	for(int i=1;i<=n;i++){
		s[i] = s[i-1]+miu[i];
	}
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n');
	ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0);
	mobi(nn-3);
	int n;
	cin>>n;
	int a,b,d;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>d;
		int ta = a/d,tb = b/d;
		int tn = min(ta,tb);
		// 实际上就是求gcd(ta,tb)==1
		ll ans = 0;
		for(int l=1,r;l<=tn;l=r+1){
			r = min(tn,min(ta/(ta/l),tb/(tb/l)));
			ans+=(s[r]-s[l-1])*(ll)(ta/l)*(ll)(tb/l);
		}
		cout<<ans<<endl;
	}
}