#include <iostream> #include <cmath> #include <vector> using namespace std; vector<long long>v; int main() { ios_base::sync_with_stdio(0); long long t; cin>>t; long long przypadek[t]; long long max=0; for (long long k=0;k<t;k++) { cin>>przypadek[k]; if (przypadek[k]>max) { max=przypadek[k]; } } v.push_back(1); v.push_back(2); long long i=2; long long x=v[i-2]+v[i-1]; while (x<=max) { v.push_back(x); i++; x=v[i-2]+v[i-1]; } bool wyn[t]; for (long long k=0;k<t;k++) { wyn[k]=0; if (przypadek[k]==0) { wyn[k]=1; } else { long long pier=sqrt(przypadek[k]); long long l=0; bool ok=0; while (v[l]<=pier) { if (przypadek[k]%v[l]==0) { x=przypadek[k]/v[l]; long long b=l,e=i-1; long long s=(b+e)/2; while (b<=e) { if (v[s]==x) { wyn[k]=1; ok=1; break; } if(v[s]<x) { b=s+1; } else { e=s-1; } s=(b+e)/2; } if (ok==1) { break; } } l++; } } } for (long long k=0;k<t;k++) { if (wyn[k]==1) { cout<<"TAK"<<"\n"; } else { cout<<"NIE"<<"\n"; } } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 | #include <iostream> #include <cmath> #include <vector> using namespace std; vector<long long>v; int main() { ios_base::sync_with_stdio(0); long long t; cin>>t; long long przypadek[t]; long long max=0; for (long long k=0;k<t;k++) { cin>>przypadek[k]; if (przypadek[k]>max) { max=przypadek[k]; } } v.push_back(1); v.push_back(2); long long i=2; long long x=v[i-2]+v[i-1]; while (x<=max) { v.push_back(x); i++; x=v[i-2]+v[i-1]; } bool wyn[t]; for (long long k=0;k<t;k++) { wyn[k]=0; if (przypadek[k]==0) { wyn[k]=1; } else { long long pier=sqrt(przypadek[k]); long long l=0; bool ok=0; while (v[l]<=pier) { if (przypadek[k]%v[l]==0) { x=przypadek[k]/v[l]; long long b=l,e=i-1; long long s=(b+e)/2; while (b<=e) { if (v[s]==x) { wyn[k]=1; ok=1; break; } if(v[s]<x) { b=s+1; } else { e=s-1; } s=(b+e)/2; } if (ok==1) { break; } } l++; } } } for (long long k=0;k<t;k++) { if (wyn[k]==1) { cout<<"TAK"<<"\n"; } else { cout<<"NIE"<<"\n"; } } } |