题解 - [AtCoder ARC051B] 互除法

题目链接

题意简述

给出 \(n\), 输出一组数 \(a,b\), 使得 gcd(a, b) 的递归次数为 \(n\)

其中 gcd(a, b) 定义如下,counter 即为递归次数

解题思路

考虑欧几里得算法的最坏情况,即 a,b 为两个相邻的斐波那契数

\(T(a,b)\) 为对 \(a,b\)\(gcd\) 递归层数

Fibonacci 数列

\[ F_n:=\begin{cases} 1,& n\leqslant 1\\ F_{n-1}+F_{n-2},& n>1 \end{cases} \]

则有

\[ T(F_{n-1},F_n)=n \]

用数学归纳法可以证明

所以只需要输出 \(F_{n-1}\)\(F_n\) 即可