Fişierul intrare/ieşire:fibocel.in, fibocel.outSursăUrmasii lui Moisil 2016, Clasa a 10-a
AutorCosmin-Mihai TutunaruAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test1.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fibocel

Toata lumea ştie că Fibocel este pasionat de numere şi că vrea să iasă în evidenţă cu orice preţ. Într-o zi, el s-a decis să numească un număr fibocel (după numele lui) dacă numărul de biţi egali cu 1 din reprezentarea binară a numărului este un număr Fibonacci.

Cum asta nu e de ajuns pentru el, Fibocel s-a decis să propună şi o problemă la concursul lui preferat de la Iaşi.

Cerinţă

Să se raspundă la Q întrebări de forma: Câte numere fibocel există în intervalul închis [A, B] ?

Date de intrare

Fişierul de intrare fibocel.in conţine pe prima linie numărul natural Q, iar pe următoarele Q linii se găsesc câte două numere naturale A şi B separate prin exact un spaţiu, reprezentând extremităţile intervalului la care se referă întrebarea.

Date de ieşire

Fişierul de ieşire fibocel.out va conţine exact Q numere, câte unul pe o linie, reprezentând răspunsurile la cele Q întrebări, în ordinea în care ele apar în fişierul de intrare.

Restricţii

  • 1 ≤ Q ≤ 50.000
  • 1 ≤ AB ≤ 1015
  • Şirul Fibonacci se defineşte astfel: F0=F1=1; Fn=Fn-1+Fn-2, pentru n ≥ 2
  • Pentru 40% din teste B ≤ 1.000.000

Exemplu

fibocel.infibocel.outExplicaţie
1
15 16
1
15(10)=1111(2) nu este fibocel (are 4 biţi de 1 iar 4 nu este număr Fibonacci)
16(10)=10000(2) este fibocel (are 1 bit de 1 iar 1 este număr Fibonacci)
7
1 13
13 31
13 131
31 131
131 313
313 1313
1313 3131
13
14
76
63
97
421
667
.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?