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 118 119 120 121 122 123 124 125 126 127 128 #include #include using namespace std; int64_t power(int64_t a, int64_t n, int64_t mod) { int64_t power = a; int64_t result = 1; while (n) { if (n & 1) result = (result * power) % mod; power = (power * power) % mod; n >>= 1; } return result; } // n−1 = 2^s * d with d odd by factoring powers of 2 from n−1 bool witness(int64_t n, int64_t s, int64_t d, int64_t a) { int64_t x = power(a, d, n); int64_t y; while (s) { y = (x * x) % n; if (y == 1 && x != 1 && x != n - 1) return false; x = y; --s; } if (y != 1) return false; return true; } /* * if n < 1,373,653, it is enough to test a = 2 and 3; * if n < 9,080,191, it is enough to test a = 31 and 73; * if n < 4,759,123,141, it is enough to test a = 2, 7, and 61; * if n < 1,122,004,669,633, it is enough to test a = 2, 13, 23, and 1662803; * if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11; * if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13; * if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17. */ bool is_prime_mr(int64_t n) { if (((!(n & 1)) && n != 2) || (n < 2) || (n % 3 == 0 && n != 3)) return false; if (n <= 3) return true; int64_t d = n / 2; int64_t s = 1; while (!(d & 1)) { d /= 2; ++s; } if (n < 1373653) return witness(n, s, d, 2) && witness(n, s, d, 3); if (n < 9080191) return witness(n, s, d, 31) && witness(n, s, d, 73); if (n < 4759123141) return witness(n, s, d, 2) && witness(n, s, d, 7) && witness(n, s, d, 61); if (n < 1122004669633) return witness(n, s, d, 2) && witness(n, s, d, 13) && witness(n, s, d, 23) && witness(n, s, d, 1662803); if (n < 2152302898747) return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11); if (n < 3474749660383) return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11) && witness(n, s, d, 13); return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11) && witness(n, s, d, 13) && witness(n, s, d, 17); } const int64_t pows[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000 }; bool validate(int64_t left, int64_t right) { return is_prime_mr(right) && is_prime_mr(left); } bool test(int64_t n) { int64_t right = 0; int64_t pow_index = 0; while(n > 0) { int64_t num = n % 10; right += pows[pow_index] * num; n /= 10; pow_index++; if(num != 0 && validate(n, right)) { return true; } } return false; } int main() { ios_base::sync_with_stdio(false); int64_t num; cin >> num; cout << (test(num) ? "TAK" : "NIE"); return 0; }