P4918 打节拍（基础）

解题思路

第一步，理解题意。 左边的A观众每x秒打一次节拍，右边的B观众每y秒打一次节拍，每次打节拍持续1秒。问在n秒之内，一共有多少秒有人在打节拍。如果某1秒里A和B同时打，这一秒只能算一次。

第二步，先算A的节拍数。 A在第x秒、第2x秒、第3x秒……各打一次，每次持续1秒，所以在n秒之内A打的次数是n除以x的整数部分。同理，B打的次数是n除以y的整数部分。

第三步，去掉重复计算的秒数。 如果直接把两个数加起来，那么A和B同时打的那几秒被算了两遍，要减掉一次。A和B同时打的时刻是x和y的公倍数，也就是最小公倍数lcm的倍数，所以同时打的次数是n除以lcm。

第四步，容斥原理。 答案等于n/x加上n/y再减去n/lcm。这就是容斥原理：先加A的，再加B的，最后减去两边重合的部分。例如样例x=2、y=3、n=10：A打10除以2等于5次，B打10除以3等于3次，同时打10除以6等于1次，答案5+3-1=7，和样例一致。

第五步，求最小公倍数。 最小公倍数lcm等于x除以最大公约数再乘y，其中最大公约数用辗转相除法求。注意要先除再乘，防止中间结果超出范围。题目没有给数据范围，保险起见全部用long long。

参考代码

// 打节拍：容斥原理，总秒数等于A的节拍加B的节拍再减去同时打的重叠部分
#include <iostream>
using namespace std;
long long gcd(long long a, long long b) {
    while (b) { long long t = a % b; a = b; b = t; }
    return a;
}
int main() {
    long long x, y, n;
    cin >> x >> y >> n;
    long long lcm = x / gcd(x, y) * y; // 同时打节拍的周期
    cout << n / x + n / y - n / lcm << endl;
    return 0;
}

复杂度分析

主要计算是一次求最大公约数，时间复杂度O(log max(x,y))，其他都是常数时间，所以总时间复杂度O(log max(x,y))，几乎是瞬间完成。空间上只用几个变量，空间复杂度O(1)。无论x、y、n多大都能轻松处理。