自动搬运

查看原文

来自洛谷，原作者为

	xinxin2022 江畔何人初见月，江月何年初照人。||主页：https://www.luogu.com/paste/tvmkisij

搬运于2025-08-24 21:17:56，当前版本为作者最后更新于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;
}