CF1389E

入手

因为星期几有周期性，可以转化为同余问题。

(x-1)d+(y-1) \equiv (y-1)d+(x-1) \pmod{w}

移项并因式分解得：

(x-y)(d-1)\equiv 0 \pmod{w}

我们将

x-y

改为

y-x

，因为题目中

y>x

：

(y-x)(d-1)\equiv 0 \pmod{w}

也就是：

w \mid (y-x)(d-1)

现在请读者将

(y-x)

当作未知数来求解这个方程，求出未知数的范围，然后你或许就能解出这道题了。

两边同除

\gcd(w,d-1)

：

\frac{w}{\gcd(w,d-1)} \mid \frac{(y-x)(d-1)}{\gcd(w,d-1)}

因为

\frac{w}{\gcd(w,d-1)}\perp \frac{d-1}{\gcd(w,d-1)}

所以只能是：

\frac{w}{\gcd(w,d-1)} \mid (y-x)

我们换个元，令

D=\frac{w}{\gcd(w,d-1)}

。

此时，我们可以将问题简化了：
存在多少个数对

(x,y)

，满足：

1 \leq x < y \leq \min(m, d), \\ D \mid (y - x). \end{cases}$$ 这个问题已经非常简单了，我们已经将一道蓝题转化为橙题了！ 但你如果还需要做法： 令 $L=[1,\min(m, d)]$。 1. $y-x\leq 0$ 时，不满足 $x<y$ 2. $y-x=D$ 的贡献为 $L-D$。 3. $y-x=2D$ 的贡献为 $L-2D$。 4. $y-x=kD$ 的贡献为 $L-kD$。 计算最大可能的 $k$，并将前 $k$ 项贡献使用等差数列求和来算总贡献。 ## 代码 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; ll m,d,w; ll gcd(ll a,ll b){return (!b?a:gcd(b,a%b));} ll solve(){ scanf("%lld%lld%lld",&m,&d,&w); ll L=min(m,d);// 指 x,y 介于 [1,L] ll D=w/gcd(d-1,w);// D | y-x; ll cnt=L/D;// 即上文中最大的 k ll ans=cnt*L-D*(cnt+1)*cnt/2; return ans; } signed main(){ int T;scanf("%d",&T); while(T--)printf("%lld\n",solve()); } ```