分析

即求 \[ (x-1)d + y \equiv (y-1)d + x \pmod w \] 满足 \(x < y\) 的解 \((x,y)\) 的个数。

化简 \[ xd + y \equiv yd + x \pmod w \]

\[ yd - xd - x -y \equiv 0 \pmod w \]

\[ (y-x)(d-1) \equiv 0 \pmod w \]

设 \(w' = \frac{w}{\gcd(w,d-1)}\)，那么有 \[ y-x \equiv 0 \pmod {w'} \] 考虑 \(y-x = k w'\)。当 \(k\) 为定值时，由于 \(y-x \in [1,\min(d,m)]\)，所以数量为 \(\min(d,m) - kw'\)。

答案即为 \[ \sum_{k=1}^{\lfloor \frac{\min(d,m)}{w'} \rfloor} \min(d,m) - kw' \] 发现这是个等差数列，直接求和即可。

首项 \(\min(d,m) - kw'\)，末项 \(\min(d,m) - \lfloor \frac{\min(d,m)}{w'} \rfloor w'\)，公差 \(\lfloor \frac{\min(d,m)}{w'} \rfloor\)。

答案 \[ \frac{\big(2 \min(d,m) - \lfloor \frac{\min(d,m)}{w'} \rfloor w' - w'\big) \cdot \lfloor \frac{\min(d,m)}{w'} \rfloor }{2} \]

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int t, m, d, w;
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();		
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a;
}
int gcd(int x,int y) { return y? gcd(y,x%y):x; }
void solve() {
	m=read(), d=read(), w=read();
	int ans=0;
	w/=(gcd(d-1,w));
	int mn=min(m,d), cnt=mn/w;
	ans=(2*(mn-w)-w*(cnt-1))*cnt/2;
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}