Written by @Yue_chen

题意：

由题意化简得出式子：

$(x-y)*(d-1)$；$d$, $w$ 已经给出，$x$，$y$的上界也分别给出。

求满足上式的二元组 $(x, y)$ 的数量。

思路：

式子化简由题意给出的两个式子相减得到，不再赘述。

由于 $y > x$，设 $T = y-x$，$T$ 的范围为[1, min(m, d)-1]，得到：

T * (d - 1) % w == 0

设 g = gcd(d-1, w)，将w/g，此时d-1 与 (w/g)互质，直接消掉，得到：

T % (w/g) == 0

我们发现T的数量就是(w/g)的所有倍数。

由于我们有了T的范围，所以可以直接用 T/ (w/g) 得到T的数量cnt[T]。

对于每一个T，他的贡献为 min(m, d) - T;

可以发现，随着T的增大，cnt的值是一个等差数列。

因此直接使用等差数列求和公式解决该问题。

最终答案ans = min(m,d) * cnt[T] - (cnt[T] * (cnt[T] -1) / 2 * T);

时间复杂度O(1)

AC代码：

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
constexpr i64 M = 1e9;

void solve() {
    i64 m, d, w; cin>>m>>d>>w;
    i64 k = w / gcd(d-1, w);
    i64 q = min(m, d) / k;
    cout<<(min(m, d) * q - (q + 1) * q / 2 * k)<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1; cin>>t;
    while (t--) solve();
    return 0;
}