B4077 [CSP-X2019 山东] 鼓掌

chen_zhe · 2024-12-15 19:30:34 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

本题考查数论。

（超时做法） 使用循环结构，让变量 i 从第 1 秒循环到第 n 秒。每 x 秒鼓掌一次就是指 i 能够被 x 整除的时候鼓掌，每 y 秒鼓掌一次同理。因此编写一个循环，统计有多少个这样的 i 即可。

参考代码（部分）：

for (int i = 1; i <= n; i++) {
    if (i % x == 0 || i % y == 0)
        cnt++;
}

这样的代码会 TLE（超时），是因为题目中的 n 最大可以到 10^9，计算机一秒钟运行不了那么多运算。因此，我们需要优化计算流程。

（正确做法）

我们可以使用数学方式统计有多少秒鼓掌。

在 n 秒内，A 班每 x 秒鼓掌一次，一共会鼓掌 \lfloor \dfrac{n}{x} \rfloor 次，其中 \lfloor \rfloor 表示下取整，例如 \lfloor 3.14 \rfloor=3，写作代码就是 n / x（n 和 x 都是整型变量）

在 n 秒内，B 班每 y 秒鼓掌一次，一共会鼓掌 \lfloor \dfrac{n}{y} \rfloor 次。

但是，A 班和 B 班会有重叠的鼓掌时间，重叠的周期即为 x,y 的最小公倍数，即 \operatorname{lcm}(x,y)。最小公倍数指的是，最小的正整数 k，使得 x,y 能同时整除 k，例如 2,3 的最小公倍数是 6，4,6 的最小公倍数是 12。

因此，额外减去 \lfloor \dfrac{n}{\operatorname{lcm}(x,y)} \rfloor 次鼓掌即可。问题在于如何求出 \operatorname{lcm}(x,y) 呢？实际上我们可以求出最大公约数 \gcd(x,y)（即：最大的正整数 k，使得 k 能同时整除 x,y，例如 6 和 9 的最大公约数是 3），然后使用这个转化公式，即可求出 \operatorname{lcm}(x,y) 了：

最大公约数如何求出呢？有三种做法。

• 第一种做法是编写一个循环，让循环变量 z 从 x 和 y 中的最小值开始不断自减，逐个判断是否能够同时满足 x % z == 0和 y % z == 0，若能满足则第一个被发现的 z 就是最大公约数。这种做法效率最慢，但是足以通过本题。
• 第二种做法是使用辗转相除法，利用性质 \gcd(x,y)=\gcd(y,x \bmod y) 进行递归，从而快速计算出最大公约数，运算效率比第一种做法快。
• 第三种做法是使用库函数 __gcd(x, y)（仅限 G++ 编译器）或者 std::gcd(x, y)（仅限 C++17 以后的语言标准，头文件为 numeric）计算，这个做法效率上和第二种做法可以认为是一致的，但是正式赛无法使用 std::gcd(x, y)。

参考代码：

int gcd(int x, int y) { //第一种做法
    int z = min(x, y);
    while (!(x % z == 0 && y % z == 0)) 
        z--;
    return z;
}

int gcd(int x, int y) { //第二种做法
    return !y ? x : gcd(y, x % y);
}

cout << n / x + n / y - n / (x / gcd(x, y)*y) << endl;