题解：B4221 [常州市程序设计小能手 2023] 红绿灯

xinxin2022 · 2025-03-12 20:39:31 · 题解

直接做显然不好做，发现时间长度为 2pq，考虑与解法有何关联。

显然当 p\perp q 时，由于存在红灯和绿灯两种状态，可以使两个灯回到同一起点的时间为 2pq。

而若 p,q 不互质，那么相当于有 \gcd(p,q) 段连续时间两灯状态会相等，可以先同时除去 \gcd(p,q)，计算出答案后再乘上 \gcd(p,q)^2，也就是被除掉的部分。

那么对于 p\perp q，计算答案的方式如下：

易知 p,q 不会都是偶数。

考虑分类讨论前 pq 秒和后 pq 秒。

若存在一个偶数，那么相当于该灯在前 pq 秒中奇数次改变了状态，那么前 pq 秒和后 pq 秒状态显然相反，另一个灯状态确却是相等的，那么相当于该灯补上了前 pq 秒的空缺时间，计算出另一个灯在 pq 秒内的绿灯时间即可，即 \frac{pq}{2}。

若都为奇数，两灯在前 pq 秒和后 pq 秒的状态均相反，只需要知道 pq 秒内的答案即可。

由于两数均为奇数，p 改变状态时会覆盖 q 同色连续段的所有点，而 p\to p+1 显然只会使一个同色点改为异色点，一个异色点改为同色点，显然不对答案产生影响。

考虑计算 pq 秒内所有 p 的改变，因所有改变状态点均被扫到，绿灯时长自然为 \frac{p(q+1)}{2}。

对 q 的改变计算也同理，时长为 \frac{q(p+1)}{2}。

由于两数均为奇数，前 pq 秒状态与后 pq 秒相反，答案如下：

即：

所以答案为：

最后乘上 \gcd(p,q)^2 即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int p,q,w;
signed main(){
    cin>>p>>q;
    w=__gcd(p,q);
    p/=w;
    q/=w;
    if((p%2)&&(q%2)) cout<<w*w*((p*q+1)/2);
    else cout<<w*w*(p*q)/2;
    return 0;
}