整齐的座位号

解题思路

同时能被a、b整除的编号，恰好是它们的最小公倍数lcm的倍数。先用欧几里得算法求g=gcd(a,b)，再算lcm=(a/g)*b，答案为n/lcm的整数商。

例如a=2、b=3时lcm=6，1～20中的符合者是6、12、18，共20/6=3个。

正确性说明

最小公倍数整除所有公倍数且本身能被a、b整除，因此符合座位与lcm正倍数一一对应。不超过n的倍数个数按整数商计算即正确。

易错点

先除g再乘b可减小中间值；lcm>n自然得到0；C++11没有std::gcd，手写循环。

复杂度

时间O(log min(a,b))，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, a, b;
    cin >> n >> a >> b;
    long long x = a, y = b;
    while (y) {
        long long r = x % y;
        x = y;
        y = r;
    }
    long long multiple = a / x * b;
    cout << n / multiple << "\n";
    return 0;
}