2023 Hubei Provincial Collegiate Programming Contest

Problem I - Step

题目描述

给定 $n$ 个环，第 $i$ 个环的长度为 $p_i$。每个环的 $1$ 号位置一开始都有一匹小马，小马第 $k$ 天会移动 $k$ 步。

要求找到最早的一天 $m$，使得所有小马都回到各自环上的 $1$ 号位置。这里 $m$ 不能为 $0$。

输入

第一行包含一个正整数 $n$，表示环的数量，满足 $1 \le n \le 10^5$。

第二行包含 $n$ 个正整数 $p_i$，表示每个环的长度，满足 $1 \le p_i \le 10^7$。

保证 $p_1,p_2,\ldots,p_n$ 的最小公倍数不超过 $10^{18}$。

输出

输出一个正整数，表示所有小马同时回到位置 $1$ 的最早日期。

分析

第 $m$ 天结束时，小马总共移动的步数为：

$$1+2+\cdots+m=\frac{m(m+1)}{2}$$

对于每个环，都需要满足：

$$\frac{m(m+1)}{2} \equiv 0 \pmod {p_i}$$

因此可以先把所有 $p_i$ 合并成一个模数条件，再根据奇偶性和整除关系处理 $m$ 与 $m+1$。这类题的关键是把“每天移动步数递增”转化为三角数取模问题。