Có phải số Fibo?

Xem PDF
Tác giả:
PhanDinhKhoi
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Bạn được cho 1 số nguyên dương \(N\). Hãy viết chương trình kiểm tra \(N\) có phải số Fibo hay không ?

Biết rằng số Fibo là số thuộc trong dãy số có quy luật như sau: \(0, 1, 1, 2, 3, 5, 8, 13, ...\)

Input

  • Dòng đầu tiên chứa số nguyên \(T \ (T \leq 10^5)\) – là số câu hỏi

  • \(T\) dòng tiếp theo,mỗi chứa 1 số nguyên dương \(N\) \((1 \leq N \leq 10^{10})\)

Output

  • \(T\) dòng, in ra IsFibo nếu N là số Fibo, ngược lại in ra IsNotFibo

Example

Test 1

Input 
3
5
7
8
Output 
IsFibo
IsNotFibo
IsFibo

Bình luận


  • 9
    jumptozero    11:50 p.m. 1 Tháng 7, 2020 ← chỉnh sửa 2

    \(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

    \(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

    \(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

    ---

    \(\color{orange}{\text{Hint }}\)

    • Dùng set để lưu tất cả các số Fibonacci bé hơn \(1e10\)
    • Dùng phương thức find của set để kiểm tra một số có phải là số Fibonacci hay không ?

    \(\color{green}{\text{Preference AC Code }}\): Online Solving

    \(^{^{\color{purple}{\text{Complexity : }} O(t*log(n))\ \color{purple}{\text{time}}\ \color{purple}{\text{memory}}}}\)

    C++
    #include<bits/stdc++.h>
using namespace std;
#define ll long long 
set<ll> s;
set<ll>::iterator it;
ll a,b,c,i,n,t;
int main(){
    a=0,b=1;
    s.insert(1);
    while(1){
        c=b;
        b=b+a;
        a=c;
        s.insert(b);
        if(b>(ll)(1e10)) break;
    }
    cin>>t;
    while(t--){
        cin>>n;
        it=s.find(n);
        if(it==s.end()) cout<<"IsNotFibo"<<'\n';
        else cout<<"IsFibo"<<'\n';
    }
    return 0;
}
    2 phản hồi