#include <cstdio> using namespace std; bool bin_search(int t[], int x, int p, int k) { if (k - p + 1 <= 2) { if ((t[p] == x || t[k] == x)) { return true; } else { return false; } } else { if (t[(p+k)/2] > x) { return bin_search(t, x, p, (p+k)/2); } else { return bin_search(t, x, (p+k)/2, k); } } } long long fib(int n) { long long i = 1, j = 0, k = 0, h = 1, t = 0; while (n > 0) { if (n % 2 == 1) { t = (j * h); j = (i * h + j * k + t); i = (i * k + t); } t = (h * h); h = (2 * k * h + t); k = (k * k + t); n /= 2; } return j; } int main() { int t, n, f[50], d, ile; unsigned int j, g, k; bool stan; for (int i = 0; i <= 45; i++) f[i] = fib(i); scanf("%d", &t); for (int i = 0; i < t; i++) { scanf("%d", &n); j = 2; k = 1; d = -1; ile = 0; stan = true; while (j*j <= n) { while (!(n % j)) { ile++; if (bin_search(f, j, 0, 45) == false || ile > 2) { stan = false; break; } n /= j; } if (n == 1) break; if (j < 3) j++; else { j = 6 * k + d; if (d == 1) { d = -1; k++; } else d = 1; } } if (n > 1) { ile++; if (bin_search(f, n, 0, 45) == false) stan = false; } if (ile > 2) stan = false; if (stan == false) printf("NIE\n"); else printf("TAK\n"); } return 0; }
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 | #include <cstdio> using namespace std; bool bin_search(int t[], int x, int p, int k) { if (k - p + 1 <= 2) { if ((t[p] == x || t[k] == x)) { return true; } else { return false; } } else { if (t[(p+k)/2] > x) { return bin_search(t, x, p, (p+k)/2); } else { return bin_search(t, x, (p+k)/2, k); } } } long long fib(int n) { long long i = 1, j = 0, k = 0, h = 1, t = 0; while (n > 0) { if (n % 2 == 1) { t = (j * h); j = (i * h + j * k + t); i = (i * k + t); } t = (h * h); h = (2 * k * h + t); k = (k * k + t); n /= 2; } return j; } int main() { int t, n, f[50], d, ile; unsigned int j, g, k; bool stan; for (int i = 0; i <= 45; i++) f[i] = fib(i); scanf("%d", &t); for (int i = 0; i < t; i++) { scanf("%d", &n); j = 2; k = 1; d = -1; ile = 0; stan = true; while (j*j <= n) { while (!(n % j)) { ile++; if (bin_search(f, j, 0, 45) == false || ile > 2) { stan = false; break; } n /= j; } if (n == 1) break; if (j < 3) j++; else { j = 6 * k + d; if (d == 1) { d = -1; k++; } else d = 1; } } if (n > 1) { ile++; if (bin_search(f, n, 0, 45) == false) stan = false; } if (ile > 2) stan = false; if (stan == false) printf("NIE\n"); else printf("TAK\n"); } return 0; } |