fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define name "FIBO"
  5. const int MAXX = 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. bool F[MAXX];
  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. void tao_mang_Fibonacci(){
  38.     memset(F, false, sizeof(F)); // Đặt tất cả các số trong mảng thành false
  39.     F[1] = true; // Đặt số 1 là true (số 1 thuộc dãy fibonacci)
  40.     int a = 1, b = 1, c = a + b;
  41.     while (c < MAXX){
  42.         F[c] = true; // Đặt c là true (c thuộc dãy fibonacci)
  43.         a = b; b = c;
  44.         c = a + b;
  45.     }
  46. }
  47.  
  48. void cach2(){
  49.     cin >> x;
  50.     if (F[x] == true) cout << "YES\n"; // Kiểm tra, nếu đúng thì in ra YES
  51.     else cout << "NO\n";
  52.  
  53. }
  54.  
  55. int main(){
  56.     setIO(); // Nhập xuất file
  57.     cin >> q;
  58.     tao_mang_Fibonacci();
  59.     for (int i = 0; i<q; i++) cach2();
  60. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
1
8
9
2584
27
stdout
copy 
YES
YES
NO
YES
NO
https://ideone.com/GFGsi5
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!