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;
}

    • 5
      SPyofgame    6:04 a.m. 2 Tháng 7, 2020 ← đã chỉnh sửa

      By the way, có một cách khác để tiếp cận đó là

      \(n\) là số fibonacci \(\Leftrightarrow\) \((5 * n ^ 2 + 4)\) hoặc \((5 * n ^ 2 – 4)\) là số chính phương


      • 5
        jumptozero    6:29 a.m. 2 Tháng 7, 2020

        \(5n^2+4\) và \(5n^2-4\) kiểm tra số chính phương có vẻ khó vì \(n\sim 1e10\) !


      • 9
        SPyofgame    5:58 a.m. 2 Tháng 7, 2020
        • Bản thân \(std::set\) cũng có thể hiểu là một mảng sắp xếp các phần tử phân biệt.

        Trong bài trên mình chỉ sử dụng các phần tử phân biệt để chèn vào. Mà các phần tử cũng được sắp xêp tăng dần rồi nên ta cũng có thể lưu vào một mảng khác (ví dụ \(fibonacci[]\))

        • Việc tìm kiếm \(std::set::find\) cũng có thể hiểu là phương pháp chặt nhị phân

        Lúc này ta chỉ cần chặt nhị phân kiểm tra xem có tồn tại phần tử \(query_i\) hay không trong mảng \(fibonacci[]\)

        • Vậy bài hướng dẫn trên, dựa trên cơ sở kiến thức và template của mình thì mình nghĩ editorial-writter jumptozero có thể điều chỉnh một chút xíu để hướng tới mọi người hơn, cả những người mới chỉ học cơ bản mà chưa quen sử dụng \(STL - Standard\ Template\ Library\)
          hể

        Thêm vào phần Hint những gợi ý hướng tới thuật toán giải bài hơn là những lời giải thích code (ví dụ "Dùng một mảng để lưu các số fibonacci tăng dần")

        Thêm vào phần Approach hoặc comment vào trong code lời giải những đoạn code cần giải thích, hay được nhắc tới trong Hint, hay có thể mọi người không chú ý để điều chỉnh tốt hơn

        Thêm vào phần Code độ phức tạp để mọi người có thể đánh giá hướng giải này thế nào so với bản thân hay đại loại vậy