#include <array> #include <iostream> class { typedef uint64_t u64; typedef uint64_t s64; s64 MultiplyMod(s64 a, s64 b, s64 mod) { //computes a * b % mod u64 r = 0; a %= mod, b %= mod; while (b) { if (b & 1) r = (r + a) % mod; b >>= 1, a = ((u64) a << 1) % mod; } return r; } template<typename T> T PowerMod(T a, T n, T mod) { // computes a^n % mod T r = 1; while (n) { if (n & 1) r = MultiplyMod(r, a, mod); n >>= 1, a = MultiplyMod(a, a, mod); } return r; } template<typename T> bool isprime(T n) { // deterministic Miller-Rabbin // determines if n is a prime number const int pn = 9, p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23}; for (int i = 0; i < pn; ++i) if (n % p[i] == 0) return n == p[i]; if (n < p[pn - 1]) return 0; T s = 0, t = n - 1; while (~t & 1) t >>= 1, ++s; for (int i = 0; i < pn; ++i) { T pt = PowerMod<T>(p[i], t, n); if (pt == 1) continue; bool ok = 0; for (int j = 0; j < s && !ok; ++j) { if (pt == n - 1) ok = 1; pt = MultiplyMod(pt, pt, n); } if (!ok) return 0; } return 1; } public: bool run() { std::cin >> std::ws; // no leading zeroes if (std::cin.peek() == '0') return false; std::cin >> num; ///////////////////////////////////////////////////////////// u64 leftpart = 0, rightpart, leftcheck; for (u64 pow10 = 1; pow10 < num; pow10 *= 10) { leftcheck = leftpart; leftpart = num / pow10; rightpart = num - (leftpart * pow10); // detect and omit leading zeroes if (leftcheck == (leftcheck / 10) * 10) continue; if (isprime<u64>(rightpart) && isprime<u64>(leftpart)) return true; } return false; } u64 num; } m; int main() { std::cout << (m.run() ? "TAK" : "NIE"); };
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 | #include <array> #include <iostream> class { typedef uint64_t u64; typedef uint64_t s64; s64 MultiplyMod(s64 a, s64 b, s64 mod) { //computes a * b % mod u64 r = 0; a %= mod, b %= mod; while (b) { if (b & 1) r = (r + a) % mod; b >>= 1, a = ((u64) a << 1) % mod; } return r; } template<typename T> T PowerMod(T a, T n, T mod) { // computes a^n % mod T r = 1; while (n) { if (n & 1) r = MultiplyMod(r, a, mod); n >>= 1, a = MultiplyMod(a, a, mod); } return r; } template<typename T> bool isprime(T n) { // deterministic Miller-Rabbin // determines if n is a prime number const int pn = 9, p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23}; for (int i = 0; i < pn; ++i) if (n % p[i] == 0) return n == p[i]; if (n < p[pn - 1]) return 0; T s = 0, t = n - 1; while (~t & 1) t >>= 1, ++s; for (int i = 0; i < pn; ++i) { T pt = PowerMod<T>(p[i], t, n); if (pt == 1) continue; bool ok = 0; for (int j = 0; j < s && !ok; ++j) { if (pt == n - 1) ok = 1; pt = MultiplyMod(pt, pt, n); } if (!ok) return 0; } return 1; } public: bool run() { std::cin >> std::ws; // no leading zeroes if (std::cin.peek() == '0') return false; std::cin >> num; ///////////////////////////////////////////////////////////// u64 leftpart = 0, rightpart, leftcheck; for (u64 pow10 = 1; pow10 < num; pow10 *= 10) { leftcheck = leftpart; leftpart = num / pow10; rightpart = num - (leftpart * pow10); // detect and omit leading zeroes if (leftcheck == (leftcheck / 10) * 10) continue; if (isprime<u64>(rightpart) && isprime<u64>(leftpart)) return true; } return false; } u64 num; } m; int main() { std::cout << (m.run() ? "TAK" : "NIE"); }; |