(特別)フィボナッチ数列の性質③

2 secs 1024 MB
Aozora_Kotori_A

フィボナッチ数列の各項を自然数 で割った余りを並べる数列を考えよう。これを「 の数列」と呼ぶことにする。

例えば, の数列は

であり, の数列は

である。

すると,どちらの数列もある一定の数の並びが繰り返されている事が分かる(他の数列でも試してみよう)。この繰り返しの単位における数の個数を「周期」と呼ぶことにする。

の数列は“ ”が繰り返されていて,周期は3である。 の数列は“ ”が繰り返されていて,周期は8である。

ここで, の数列の周期を求めよう。

問題文


次の問いに答えよ。ただし,フィボナッチ数列の第 項を とする。

  1. つの自然数の組 に対して, で割った余りを出力する関数 FiboMod を作成せよ。
  2. 与えられた自然数 に対して, の数列の周期を出力せよ。

ただし,必要であれば問題「フィボナッチ数列の性質①」で作成した関数 Fibonacci を利用しても構わない。利用する場合は,Fibonacci(n) の制約が であったことに注意すること。

一般に の数列の周期を求める数式は発見されておらず,そのような数式は存在しないのではないかという予想が立てられている(ウォール予想)が,現在も未解決問題となっている。

制約


  • 入力はすべて自然数

 

入力


入力は以下の形式で標準入力から与えられます。

標準入力

出力


答えの値 を以下の形式で出力してください。

標準出力

 

サンプル1

入力
11
出力
10

の数列は

となっているので,周期は10です。

 

サンプル2

入力
150
出力
600

 

関数 FiboMod に関するヒント

関数 FiboMod を,関数 Fibonacci を使用して作成すると,第46項以降を正しく出力することができません。これは,Fibonacci(n) のときにオーバーフローして正しい値を出力することができないためです。

つまり,関数 Fibonacci を使って関数 FiboMod を作成することはできないということです。

ではどうすればよいかというと,関数 Fibonacci の骨格はそのままにオーバーフローしないように関数 FiboMod を作成すればよいのです。そのためには,次の性質を使います。

性質

自然数 で割った余りがそれぞれ であるとき,すなわち であるとき,

で割った余りと で割った余りが等しい,すなわち である。

それでは,Good Luck!

提出


Go (1.14)