自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:16:55，当前版本为作者最后更新于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)$ 了：

$$\operatorname{lcm}(x,y)=\dfrac{x\times y}{\gcd(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;