版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [AtCoder ARC051B] 互除法" categories:

• 算法竞赛
• 题解 tags:
• 算法竞赛
• 题解
• AtCoder
• 数学
• 数论
• 最大公约数
• Fibonacci数列 date: 2018-07-22 19:12:06

题目链接

题意简述

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

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

{% icodeweb blog lang:cpp arc051b/gcd.cpp %}

解题思路

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

令 $T(a,b)$ 为对 $a,b$ 求 $gcd$ 递归层数

Fibonacci 数列

$$ Fn:=\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$ 即可