fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define name "FIBO"
  5. const int MAX = 2e5+5;
  6.  
  7. /*
  8. Bài này có 2 cách làm:
  9. + Cách 1 (Độ phức tạp lớn hơn, code chạy lâu hơn)
  10.     - B1: Nhập n, nhập từng truy vấn (ví dụ: Nhập số X)
  11.     
  12.     - B2: Xét từng truy vấn cộng dần các số của dãy fibonacci a, b, c = a + b
  13.       --> Kiểm tra các số a,b,c có trùng với số X không
  14.       --> Nếu trùng in ra YES, không trùng in ra NO
  15.     
  16. + Cách 2 (Độ phức tạp O(MAX) (MAX là số fibonacci cuối cùng), code chạy nhanh hơn)
  17.     - B1: Cộng dần các số Fibonacci từ 1 đến MAX (ví dụ bài này là 2*10^5 + 5)
  18.           Tạo mảng F[] (kiểu dữ liệu bool) để kiểm tra số có thuộc dãy Fibonacci không?
  19.           Ví dụ: số 3 thuộc dãy fibonacci thì: F[3] = true;
  20.     
  21.     - B2: Nhập truy vấn (VD: Nhập số X), kiểm tra F[X] == true thì in ra YES
  22.                                          else in ra NO
  23. */
  24.  
  25. int n, q, x;
  26. int F[MAX];
  27.  
  28. void setIO(){
  29.     ios_base::sync_with_stdio(0);
  30.     cin.tie(0); cout.tie(0);
  31.     if (fopen(name".inp", "r")){
  32.         freopen(name".inp", "r", stdin);
  33.         freopen(name".out", "w", stdout);
  34.     }
  35. }
  36.  
  37.  
  38. void cach1(){
  39.     cin >> x;
  40.     int a = 1, b = 1, c = 0; // a,b,c đại diện 3 số Fibonacci liên tiếp
  41.     if (x < 1) cout << "NO\n"; // Số Fibonacci không bé hơn 1 (trong yêu cầu đề)
  42.     else if (x == 1) cout << "YES\n"; // 2 Số Fibonacci đầu tiền là số 1, nên phải kiểm tra để tránh nhầm
  43.     else{
  44.         while (c < x){
  45.             c = a + b; // Quy tắc số sau bằng tổng 2 số trước của dãy số Fibonacci 
  46.             a = b; b = c;
  47.             if (x == c){ // Kiểm tra trong vòng lặp, nếu là số Fibonacci thì in ra đúng
  48.                 cout << "YES\n";
  49.                 break;
  50.             }
  51.         }
  52.         if (c > x) cout << "NO\n"; // Ra khỏi vòng lặp, phải in ra 'NO' cho kết quả sai 
  53.     }
  54. }
  55.  
  56.  
  57. // void cach2(){
  58.  
  59. // }
  60.  
  61. int main(){
  62.     setIO(); // Nhập xuất file
  63.     cin >> q;
  64.  
  65.     // Giải quyết vấn đề của đề bài đưa ra
  66.     for (int i = 0; i<q; i++){
  67.         cach1();
  68.     }
  69.     //cach2();
  70. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
5
1
8
9
2584
27
stdout
copy 
YES
YES
NO
YES
NO
https://ideone.com/5eJ1bo
language:
C++14 (clang 8.0)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!