1645 - Fibocel

Toată 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ța

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 și precizări

• 1 ≤ Q ≤ 50.000
• 1 ≤ A ≤ B ≤ 1015
• Şirul Fibonacci se defineşte astfel: , pentru
• Pentru 40% din teste B ≤ 1.000.000

Exemplul 1

fibocel.in

1
15 16

fibocel.out

1

Explicație

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)

Exemplul 2

fibocel.in

7
1 13
13 31
13 131
31 131
131 313
313 1313
1313 3131

fibocel.out

13
14
76
63
97
421
667

Rezolvare

def is_fibocel(n):
    bit_count = 0
    while n > 0:
        if n % 2 == 1:
            bit_count += 1
        n //= 2

    previous = 0
    current = 1
    while current <= bit_count:
        if current == bit_count:
            return True
        previous, current = current, previous + current

    return False

def count_fibocel_numbers(a, b):
    count = 0
    for num in range(a, b + 1):
        if is_fibocel(num):
            count += 1

    return count

def main():
    with open("fibocel.in", "r") as input_file:
        q = int(input_file.readline())

    with open("fibocel.out", "w") as output_file:
        for _ in range(q):
            a, b = map(int, input_file.readline().split())
            fibocel_count = count_fibocel_numbers(a, b)
            output_file.write(str(fibocel_count) + "\n")

if __name__ == "__main__":
    main()