2024百度之星题解 T2跑步

原题链接：跑步

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

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

一、最浅显性质分析

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

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

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

二、根据性质 b 推导公式

• 设定条件：
  设
  设 $  \forall i,j \in [1,n]  $ 且 $  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。多谢分享