P7739 [NOI2021] 密码箱的加密算法是什么？

本文共计2223个文字，预计阅读时间需要9分钟。

P7739 [NOI2021] 密码箱 题目链接：Link 本题主要思路来源于 Rikka (疯狂 + % + )。题目中的贡献值计算实际上是一个连续整数的倒数和，即：[a_1 + 1/(a_2 + 1/(a_3 + ... + 1/a_n))] 若从 (a_k) 到 (a_n)。

P7739 [NOI2021] 密码箱

题目链接： Link

本题解主要思路来源 @Rikka__(疯狂 % )。

考虑题里面的贡献的计算其实是一个连分数的倒数，即：

\[a_1+\frac {1}{a_2+\frac{1}{a_3 + ...}} \]

若从 \(a_k\) 到 \(a_1\) 从下向上合并的话能够发现其实是一个 $ \Large \frac{a'}{b'} = \frac {1}{a_i+\frac{a}{b}}$ 的形式。