駆け出しプログラマーの課題

2 secs 1024 MB
magurofly's icon magurofly

昨日駆け出したプログラマーである高橋くんは、「フィボナッチ数列を求めるプログラムを書け」という課題に取り組んでいます。

フィボナッチ数列は 0,1,1,2,0, 1, 1, 2, \ldots という無限に続く数列で、

F0=0F1=1Fn=Fn2+Fn1(n2)\begin{aligned} F_0 &= 0 \\ F_1 &= 1 \\ F_n &= F_{n - 2} + F_{n - 1} & (n \ge 2) \end{aligned}

と表されます。

目前に吐き出されるいくつものフィボナッチ数を眺めていた高橋くんは思いました。

「フィボナッチ数はとても急に大きくなるが、 3N3^N と比べるとどちらが大きくなるだろう?」

ところで、以下の問題に答えてください。

問題文

非負整数 NN に対し、 3N=Fi+Fj3^N = F_i + F_j となるような非負整数の組 (i,j)(i, j) はいくつ存在しますか?

制約

  • 0N20000 \le N \le 2000
  • 入力はすべて整数である

入力

NN

提出


Go (1.21)