2024百度之星题解 T2跑步
<h2 id="原题链接跑步">原题链接：跑步</h2><h2 id="关键词数学推公式lcm乘法逆元">关键词：数学、推公式、lcm、乘法逆元</h2>
<h3 id="算法分析环形跑道相遇次数计算问题">算法分析：环形跑道相遇次数计算问题
</h3>
<h4 id="一最浅显性质分析">一、最浅显性质分析
</h4>
<ol>
<li><strong>性质 a</strong>：跑 $m = \text{lcm}{i|i \in }$ 分钟。</li>
</ol>
<ul>
<li>其中 $\text{lcm}$ 表示最小公倍数，$m$ 为所有 1 到 n 的数的最小公倍数，确保时间足够覆盖所有周期。</li>
</ul>
<ol>
<li><strong>性质 b</strong>：相遇一定是跑的快的追上跑得慢的。</li>
</ol>
<h4 id="二根据性质-b-推导公式">二、根据性质 b 推导公式
</h4>
<ol>
<li>
<p><strong>设定条件</strong>：<br>
设 </p>
<p>设 $\forall i,j \in $ 且 $i > j$，即 $j$ 跑的比 $i$ 快。</p>
</li>
<li>
<p><strong>相遇时间推导</strong>：</p>
</li>
</ol>
<ul>
<li>当 $j$ 套 $i$ 一圈时，满足：</li>
</ul>
<p>$<br>
\frac{t}{j} - \frac{t}{i} = 1<br>
$</p>
<p>解得相遇一圈的时间：</p>
<p>$<br>
t = \frac{i \cdot j}{i - j}<br>
$</p>
<ul>
<li>在 $m$ 分钟内，$i$ 和 $j$ 相遇的次数为：</li>
</ul>
<p>$<br>
\frac{m}{t} = \frac{m(i - j)}{i \cdot j} = \frac{m}{j} - \frac{m}{i}<br>
$</p>
<h4 id="三优化计算思路">三、优化计算思路
</h4>
<ol>
<li><strong>重复计算优化</strong>：</li>
</ol>
<ul>
<li>
<p>对于每个 $x$（表示第 $x$ 个人）：</p>
<ul>
<li>
<p>有 $x-1$ 个人比 $x$ 快，对应 $-\frac{m}{x}$ 的系数为 $x-1$；</p>
</li>
<li>
<p>有 $n-x$ 个人比 $x$ 慢，对应 $\frac{m}{x}$ 的系数为 $n-x$；</p>
</li>
</ul>
</li>
<li>
<p>综上，$\frac{m}{x}$ 的总系数为：</p>
</li>
</ul>
<p>$<br>
(n - x) - (x - 1) = n - 2x + 1<br>
$</p>
<h4 id="四计算复杂度分析">四、计算复杂度分析
</h4>
<ol>
<li>**求最小公倍数 **** **：</li>
</ol>
<ul>
<li>
<p>传统方法：对每个数分解质因数，时间复杂度 $O(n\sqrt{n})$，效率较低。</p>
</li>
<li>
<p>优化思路：对于 1~n 的数，每个质因数 $p$ 的最大指数为 $\log_p n$，直接计算各质因数的最高次幂，时间复杂度 $O(1)$（宏观分析）。</p>
</li>
</ul>
<ol>
<li><strong>线性求解逆元</strong>：</li>
</ol>
<ul>
<li>用于分数计算优化，时间复杂度 $O(n)$。</li>
</ul>
<ol>
<li><strong>线性求多项式</strong>：</li>
</ol>
<ul>
<li>基于优化后的系数公式，遍历 1~n 计算各项贡献，时间复杂度 $O(n)$。</li>
</ul>
<h4 id="总结">总结
</h4>
<p>通过分析相遇性质、推导公式、优化重复计算及复杂度分析，该问题可通过线性时间算法解决，核心在于利用最小公倍数确定时间范围，并通过系数分解避免重复计算。</p>
<blockquote></blockquote><br><br>
来源：https://www.cnblogs.com/director-ni/p/18937253/BDpaobu
頁:
[1]