AGC 补题笔记

发布时间 2023-05-22 21:38:27作者: eastcloud

[AGC001]

A.BBQ Easy

由于最大数肯定要和一个比自己小的数搭配保留该数,不如选择保留次大数,如此递归即解。因此将序列排序后输出序号为奇数的数即可。

B.Mysterious Light

观察样例,考虑重复因素,即将路径长度分割成若干个个等边三角形周长总和,可以注意到每次折射的过程实际上是将大的数减去小的数的过程,直到相减为 0,这个过程就是辗转相减法。

于是会发现每条三角形长度都是计算 \(n\)\(x\) 最大公因数中辗转相减法中的一项,但是最后自己减自己那部分没有被算到答案里,即可得到答案为 \(3n-\gcd(n,x)\)