B3744 [语言月赛202304] 移植柳树 题解

· · 题解

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;
    }
}

视频讲解

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