X Round 3 补题记

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

A. 等差数列

题目链接

https://www.luogu.org/problem/P5534

题解

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

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

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

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

B. 小道消息

题目链接

https://www.luogu.org/problem/P5535

题解

题目中的提示肯定不是白给的(笑)。

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

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

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

代码就不贴了。

C. 中心城市

题目链接

https://www.luogu.org/problem/P5536

题解

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

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

(代码暂时咕咕咕)

发表评论

电子邮件地址不会被公开。 必填项已用*标注