题解 - [AtCoder ARC051B] 互除法

发表于 更新于 分类于 ， 本文字数： 149 阅读时长 ≈ 1 分钟

题目链接

题意简述

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

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

gcd.cppview raw
1
2
3
4
5
int gcd(int a, int b) {
  if (b == 0) return a;
  counter++;
  return gcd(b, a % b);
}

解题思路

考虑欧几里得算法的最坏情况，即 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\) 即可