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

2 secs 1024 MB
magurofly's icon magurofly

320003^{2000} 以下のフィボナッチ数は 45684568 個あります。

よって ii を全探索し、 jj については二分探索をします。

ただし、 Fj=1F_j = 1 のときは注意が必要です。

フィボナッチ数の計算には多倍長整数を使うと楽です。

実は、この制約下では N=0,1,2N = 0, 1, 2 のとき以外の答えは常に 00 なので、埋め込みをすることができます。