2024百度之星题解 T2跑步
原题链接：跑步关键词：数学、推公式、lcm、乘法逆元
算法分析：环形跑道相遇次数计算问题
一、最浅显性质分析
[*]性质 a：跑 $m = \text{lcm}{i|i \in }$ 分钟。
[*]其中 $\text{lcm}$ 表示最小公倍数，$m$ 为所有 1 到 n 的数的最小公倍数，确保时间足够覆盖所有周期。
[*]性质 b：相遇一定是跑的快的追上跑得慢的。
二、根据性质 b 推导公式
[*]设定条件：
设
设 $\forall i,j \in $ 且 $i > j$，即 $j$ 跑的比 $i$ 快。
[*]相遇时间推导：
[*]当 $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}
$
三、优化计算思路
[*]重复计算优化：
[*]对于每个 $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
$
四、计算复杂度分析
[*]**求最小公倍数 **** **：
[*]传统方法：对每个数分解质因数，时间复杂度 $O(n\sqrt{n})$，效率较低。
[*]优化思路：对于 1~n 的数，每个质因数 $p$ 的最大指数为 $\log_p n$，直接计算各质因数的最高次幂，时间复杂度 $O(1)$（宏观分析）。
[*]线性求解逆元：
[*]用于分数计算优化，时间复杂度 $O(n)$。
[*]线性求多项式：
[*]基于优化后的系数公式，遍历 1~n 计算各项贡献，时间复杂度 $O(n)$。
总结
通过分析相遇性质、推导公式、优化重复计算及复杂度分析，该问题可通过线性时间算法解决，核心在于利用最小公倍数确定时间范围，并通过系数分解避免重复计算。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ yyds。多谢分享
页:
[1]