Dãy Fibonacci được định nghĩa như sau:

𝐹0=𝐹1=1

𝐹𝑖=𝐹𝑖−1+𝐹𝑖−2, 𝑖≥2

Cho 𝑁 số nguyên dương, hãy xác định mỗi số đó có là số Fibonacci hay không.

Input

Dòng 1: Số nguyên dương 𝑁 (1≤𝑁≤106)

Dòng 2...𝑁+1: mỗi dòng ghi một số nguyên dương, kích thước file input không vượt quá 1MB.

Output

Dòng 1...𝑁: mỗi dòng ghi xâu "Yes" hay "No" là câu trả lời cho các số tương ứng trong input.

 

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
    int q; cin >> q; // nhập vào số lượng test
    while (q--){
        int n; cin >> n; // nhập số n
        int x1 = sqrt(5*(n * n) + 4); // điều kiện kiểm tra
        int x2 = sqrt(5*(n * n) - 4); // điều kiện kiểm tra
        if ((x1 * x1 == 5*(n * n) + 4 || x2 * x2 == 5*(n * n) - 4))
            cout << "YES\n"; // in ra YES
        else cout << "NO\n"; // in ra NO
    } // điều kiện tham khảo từ Wikipedia (đã test)
}

#include <bits/stdc++.h>
using namespace std;
bool cp (int n)
{
    int k = sqrt(n);
    return k * k == n;
}
bool check (int n)
{
    return cp(5 * n * n + 4) || cp(5 * n * n - 4);
}
int tt;
int main()
{
    cin >> tt;
    while (tt--)
    {
        int n;
        cin >> n;
        cout << (check(n) ? "YES" : "NO") << '\n';
    }   
}

Đáp án:

Giải thích các bước giải: