自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:46，当前版本为作者最后更新于2023-04-28 00:09:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2023 年 4 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

原有 $n$ 棵树，分别位于 $0, x, 2x, \cdots, (n - 1) x$ 位置（即每一棵树间隔为 $x$）。

现在想要对树做「移动」或者「删除」操作，使得这 $n$ 棵树分别位于 $0, y, 2y, \cdots, (n - 1) y$ 位置（即在起点不变的前提下让树彼此之间距离变为 $y$）。

询问有多少树可以不做「移动」或「删除」操作。

题目分析

首先，由于在操作前后树的总数不变，且无法增加树的数量，因此我们不可能执行「删除」操作。下面仅考虑「移动」操作。

我们假设原来从左向右第 $i + 1$ 棵树不需要动。这棵树的位置是 $ix$。由于移动后要求所有的树所处的位置均为 $y$ 的倍数，如果这棵树不需要移动，则需要保证 $ix$ 是 $y$ 的倍数。

因此，我们将 $i$ 从 $0$ 枚举到 $n - 1$，每次判断 $ix$ 是否是 $y$ 的倍数即可。

同时需要注意的是，在 $x < 10 ^ 6, n \leq 10 ^ 6$ 时，$ix$ 最大可以达到 $(10 ^ 6 - 1) ^ 2$，显然是 int 装不下的。因此，计算 $ix$ 时需要将其转化为 long long。

核心代码：

for (int i = 0; i < n; ++i) {
	long long p = (long long) x * i;
	if (p % y == 0) {
		++cnt;
	}
}

视频讲解

完整代码请在视频题解中查看。