A23491. 红绿灯小X家门前有两个红绿灯，小X做完了数学作业，闲着无聊便在窗边观察。他发现这两个红绿灯亮红灯和亮绿灯的时间是相等的，第一个红绿灯亮p秒绿灯，再亮p秒红灯……，第二个红绿灯亮q秒绿灯，再亮q秒红灯……，如此循环往复。现在恰好两个红绿灯都从红灯变成了绿灯，小X想要知道未来的2pq秒内，有多少秒满足两个红绿灯都亮绿灯。输入第一行2个正整数p、q，含义见题面。输出输出一行一个整数表示在未来的2pq秒…
填空题
中等
知识点
题目描述
红绿灯
小X家门前有两个红绿灯，小X做完了数学作业，闲着无聊便在窗边观察。他发现这两个红绿灯亮红灯和亮绿灯的时间是相等的，第一个红绿灯亮p秒绿灯，再亮p秒红灯……，第二个红绿灯亮q秒绿灯，再亮q秒红灯……，如此循环往复。
现在恰好两个红绿灯都从红灯变成了绿灯，小X想要知道未来的2pq秒内，有多少秒满足两个红绿灯都亮绿灯。
输入
第一行2个正整数p、q，含义见题面。
输出
输出一行一个整数表示在未来的2pq秒内，有多少秒满足两个红绿灯都亮绿灯。
样例输入1
2 3样例输入2
18 66样例输入3
1 255样例输出1
3样例输出2
612样例输出3
128提示
样例解释1
在未来的12秒内，第一个红绿灯在第1，2，5，6，9，10秒亮绿灯。
第二个红绿灯在第1，2，3，7，8，9秒亮绿灯。
在第1，2，9秒时，同时亮绿灯，一共3秒。
数据规模
对于测试点1-3：1<=p、q<=1000
对于测试点4-5：p=1, 1<=q<=10^9
对于测试点6-9：1<=p、q<=10^9 且 p、q 互质，即 p、q 的最大公约数是1
对于测试点10-12：1<=p、q<=10^9
参考答案
#include <iostream>
using namespace std;
// 最大公约数
long long gcd(long long a, long long b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}
int main() {
long long p, q;
cin >> p >> q;
long long g = gcd(p, q);
long long lcm = p / g * q; // 最小公倍数
// 2pq秒 = 2g*lcm 秒，每个周期（lcm秒）内的绿灯重叠时间为 g
cout << g * (2 * p * q / lcm) / 2 << endl;
return 0;
}
上一题
下一题