Cerința

Se citesc pe rând numere naturale nenule. Să se determine câte din numerele citite sunt termeni ai șirului lui Fibonacci.

Date de intrare

Fișierul de intrare cautafibo.in conține numere naturale nenule, separate prin spații.

Date de ieșire

Fișierul de ieșire cautafibo.out va conține o singură valoare, reprezentând numărul termenilor Fibonacci care se regăsesc în fișierul de intrare.

Restricții și precizări

• numerele din fișierul de intrare vor avea cel mult 10 cifre
• fișierul de intrare va conține cel mult 100.000 de numere naturale nenule

Exemplu

cautafibo.in

5 10 89 1 7 9 8 1 6 55 19 13 55

cautafibo.out

8

Explicație

Numerele Fibonacci din fișierul de intrare sunt: 5 89 1 8 1 55 13 55

#include <bits/stdc++.h>

using namespace std;

ifstream cin("cautafibo.in");
ofstream cout("cautafibo.out");

unsigned long long a[55] , cnt;
int n;

void fib()
{
    a[1] = 1 , a[2] = 1;
    for(n = 3 ; a[n - 1] <= 10000000001ll ; n++)
        a[n] = a[n - 1] + a[n - 2];
}

int main()
{
    fib();
    long long x;
    while(cin >> x)
    {
        unsigned long long st = 0 , dr = n - 1 , poz = -1;
        while(st <= dr)
        {
            int m =(st + dr)/2;
            if(x <= a[m])
            {
                 poz = m;
                 dr = m - 1;
            }
            else st = m + 1;
        }
        if(a[poz] == x) cnt++;
    }
    cout << cnt;
}