X Round 3 补题记 – Studying Father's blog

目录显示

我一直认为这世界没有永恒，如果非要说永恒，宇宙间唯一的永恒就是——所有的一切都会随着时光消失。

A. 等差数列

给出了序列的前两项，我们可以算出等差数列的公差 \(d=a_2-a_1\)。

进而可以根据通项公式，算出等差数列的末项 \(a_n=a_1+(n-1) \times d\)。

有了首项，末项和项数，我们就可以根据公式 \(S=\frac{(a_1+a_n) \times n}{2}\) 算出整个序列的和了。

因为代码过于简单，这里略去。

题目中的提示肯定不是白给的（笑）。

先把伯特兰-切比雪夫定理放在这吧：对于所有正整数 \(n\)，在 \((n,2n)\) 范围内至少有一个质数。

让我们对 \(k+1\) 分类讨论。

\(k+1\) 是质数，且 \(2(k+1) > n+1\)，此时 \(n+1\) 以内的其他数字全部与 \(k+1\) 互质，答案为 \(1\)；
\(k+1\) 是质数，且 \(2(k+1) \leq n+1\)，此时其他数字中存在 \(k+1\) 的倍数。根据伯特兰-切比雪夫定理，\(k+1\) 一定与不小于 \(n\) 的最大质数 \(p_{max}\)互质，且满足 \(2p_{max}>n+1\)。因此第一天结束后问题回到了第一种情况，答案为 \(2\)；
\(k+1\) 是合数，和情况 2 一样，第一天结束后问题回到了第一种情况，答案为 \(2\)。

代码就不贴了。

\(k=1\) 时，显然取树的中心（直径的中点）。

\(k>1\) 时，以树的中心为根，我们每次贪心让离城市群最远的城市距离缩短即可。

（代码暂时咕咕咕）