2024百度之星题解 T2跑步

关键词数学、推公式、lcm、乘法逆元算法分析环形跑道相遇次数计算问题一、最浅显性质分析性质 a跑 分钟。其中 表示最小公倍数 为所有 1 到 n 的数的最小公倍数确保时间足够覆盖所有周期。性质 b相遇一定是跑的快的追上跑得慢的。二、根据性质 b 推导公式设定条件设设 且 即 跑的比 快。相遇时间推导当 套 一圈时满足解得相遇一圈的时间在 分钟内 和 相遇的次数为三、优化计算思路重复计算优化对于每个 表示第 个人有 个人比 快对应 的系数为 有 个人比 慢对应 的系数为 综上 的总系数为四、计算复杂度分析**求最小公倍数 **** **传统方法对每个数分解质因数时间复杂度 效率较低。优化思路对于 1~n 的数每个质因数 的最大指数为 直接计算各质因数的最高次幂时间复杂度 宏观分析。线性求解逆元用于分数计算优化时间复杂度 。线性求多项式基于优化后的系数公式遍历 1~n 计算各项贡献时间复杂度 。总结