题解：CF1389E Calendar Ambiguity

· · 题解

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

计算最大可能的 k，并将前 k 项贡献使用等差数列求和来算总贡献。

代码

#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());
}