1 of 5

UkuNumber

@beet_aizu

2 of 5

概要

自然数のペアa, bに対しうく数列を以下のように定義する

U_1 = a, U_2 = b

U_{i+2} = U_{i+1} + U_i (1 ≤ i)

​

Xを含むうく数列の中で辞書順最小のものを求める

3 of 5

考察

自明な解を考える

{1, X-1, X, …} は明らかに条件を満たす

→ 求めるのは辞書順最小のものであるから a = 1 が確定

​

4 of 5

考察

a = 1のとき、数列はどうなるか？

{1, b, b+1, 2b+1, 3b+2, …}　

→ 各項はbの一次式になっている

U_i = X と仮定して、bに関する方程式を解く

U_100 > 10^18 なので100個試せば十分（オーバーフローに注意）

5 of 5

統計

FA: kirika_comp さん 5:39

AC rate: 98 / 111

​