2024百度之星题解 T2跑步

原题链接：跑步

关键词：数学、推公式、lcm、乘法逆元

算法分析：环形跑道相遇次数计算问题

一、最浅显性质分析

1. 性质 a：跑 $ m = ext{lcm}{i|i in [1,n]} $ 分钟。

• 其中 $ ext{lcm} $ 表示最小公倍数，$ m $ 为所有 1 到 n 的数的最小公倍数，确保时间足够覆盖所有周期。

1. 性质 b：相遇一定是跑的快的追上跑得慢的。

二、根据性质 b 推导公式

1. 设定条件：
   设

   设 $ forall i,j in [1,n] $ 且 $ i > j $，即 $ j $ 跑的比 $ i $ 快。

2. 相遇时间推导：

• 当 $ j $ 套 $ i $ 一圈时，满足：

$
frac{t}{j} - frac{t}{i} = 1
$

解得相遇一圈的时间：

$
t = frac{i cdot j}{i - j}
$

• 在 $ m $ 分钟内，$ i $ 和 $ j $ 相遇的次数为：

$
frac{m}{t} = frac{m(i - j)}{i cdot j} = frac{m}{j} - frac{m}{i}
$

三、优化计算思路

1. 重复计算优化：

• 对于每个 $ x $（表示第 $ x $ 个人）：

  • 有 $ x-1 $ 个人比 $ x $ 快，对应 $ -frac{m}{x} $ 的系数为 $ x-1 $；

  • 有 $ n-x $ 个人比 $ x $ 慢，对应 $ frac{m}{x} $ 的系数为 $ n-x $；

• 综上，$ frac{m}{x} $ 的总系数为：

$
(n - x) - (x - 1) = n - 2x + 1
$

四、计算复杂度分析

1. **求最小公倍数 **** **：

• 传统方法：对每个数分解质因数，时间复杂度 $ O(nsqrt{n}) $，效率较低。

• 优化思路：对于 1~n 的数，每个质因数 $ p $ 的最大指数为 $ log_p n $，直接计算各质因数的最高次幂，时间复杂度 $ O(1) $（宏观分析）。

1. 线性求解逆元：

• 用于分数计算优化，时间复杂度 $ O(n) $。

1. 线性求多项式：

• 基于优化后的系数公式，遍历 1~n 计算各项贡献，时间复杂度 $ O(n) $。

总结

通过分析相遇性质、推导公式、优化重复计算及复杂度分析，该问题可通过线性时间算法解决，核心在于利用最小公倍数确定时间范围，并通过系数分解避免重复计算。