BoB005-G: Butter Thief

2 secs 1024 MB
kyaneko999's icon kyaneko999

問題

Sakky さんは 11 から 1010010^{100} までの番号がついたバターを 1010010^{100} 個ずつ持っています.ii 番目のバターの美味しさは FiF_i です.
ただし,FiF_i はフィボナッチ数列の第 ii 項であり,以下のように定義されます.

  • F0=F1=1F_0=F_1=1
  • i=0,1,2,i=0,1,2,\dots に対して Fi+2=Fi+1+FiF_{i+2}=F_{i+1}+F_{i}

Sakky さんはバター泥棒に襲われやすい体質です.
バター泥棒にはそれぞれレベルが定められており,レベル XX のバター泥棒は美味しさが XX 以下のバターしか盗むことができません.
バター泥棒が Sakky さんを襲うときには,Sakky さんが持っているバターの中でなるべく美味しさが大きいものを 11 個盗みます.
レベル L,L+1,,RL,L+1,\dots,R のバター泥棒が 11 人ずつ現れ Sakky さんを襲うとき,盗まれるバターの番号の総和を求めてください.

制約

  • 入力はすべて整数
  • 1LR10161\le L\le R\le 10^{16}

入力

入力は以下の形式で標準入力から与えられる.

L  RL\;R

出力

答えを整数で出力しなさい.

入出力例

入力例1
2 5
出力例1
12

Sakky さんが持っているバターの美味しさは番号順に 1,2,3,5,8,13,1,2,3,5,8,13,\dots です.
レベル 22 のバター泥棒は美味しさが 22 以下のバターを盗むことができます.よって,Sakky さんを襲うと 22 番目のバターを盗んでいきます.
レベル 33 のバター泥棒は美味しさが 33 以下のバターを盗むことができます.よって,Sakky さんを襲うと 33 番目のバターを盗んでいきます.
レベル 44 のバター泥棒は美味しさが 44 以下のバターを盗むことができます.よって,Sakky さんを襲うと 33 番目のバターを盗んでいきます.
レベル 55 のバター泥棒は美味しさが 55 以下のバターを盗むことができます.よって,Sakky さんを襲うと 44 番目のバターを盗んでいきます.
したがって,盗まれるバターの番号の総和は 2+3+3+4=122+3+3+4=12 です.

入力例2
1 10000000000000000
出力例2
746583271651532394

提出


Go (1.21)