// Artur Kraska, II UWr #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <cmath> #include <list> #include <set> #include <map> #define forr(i, n) for(int i=0; i<n; i++) #define FOREACH(iter, coll) for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter) #define FOREACHR(iter, coll) for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter) #define lbound(P,R,PRED) ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;}) #define testy() int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests) #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define CONTAIN(el, coll) (coll.find(el) != coll.end()) #define FOR(i, a, b) for(int i=a; i<=b; i++) #define FORD(i, a, b) for(int i=a; i>=b; i--) #define MP make_pair #define PB push_back #define deb(X) X; #define M 1000000007 #define INF 1000000007 using namespace std; int n, a; int MR(long long a, long long k, long long mod) { if(k == 0) return 1; long long pom = MR(a, k/2, mod), pom2 = (pom*pom) % mod; // printf("liczy %I64d^%I64d = %I64d, kwadrat:%I64d\n", a, k/2, pom, pom2); if(pom == -1 || (pom2 == 1 && pom != 1 && pom != mod-1)) return -1; if(k&1) return (pom2*a)%mod; return pom2; } bool isPrime(long long l) { if(l <= 7) { if(l < 2) return 0; if(l == 2) return 1; return l&1; } return (MR(2, l, l) == 2) && (MR(3, l, l) == 3) && (MR(5, l, l) == 5) && (MR(7, l, l) == 7); } int main() { long long n, m = 0, dz = 1; scanf("%lld", &n); while(n > 9) { m += dz*(n%10); n /= 10; dz *= 10; if(10*m >= dz && isPrime(n) && isPrime(m)) { printf("TAK\n"); //cout << n << " " << m << endl; return 0; } } printf("NIE\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 | // Artur Kraska, II UWr #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <cmath> #include <list> #include <set> #include <map> #define forr(i, n) for(int i=0; i<n; i++) #define FOREACH(iter, coll) for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter) #define FOREACHR(iter, coll) for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter) #define lbound(P,R,PRED) ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;}) #define testy() int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests) #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define CONTAIN(el, coll) (coll.find(el) != coll.end()) #define FOR(i, a, b) for(int i=a; i<=b; i++) #define FORD(i, a, b) for(int i=a; i>=b; i--) #define MP make_pair #define PB push_back #define deb(X) X; #define M 1000000007 #define INF 1000000007 using namespace std; int n, a; int MR(long long a, long long k, long long mod) { if(k == 0) return 1; long long pom = MR(a, k/2, mod), pom2 = (pom*pom) % mod; // printf("liczy %I64d^%I64d = %I64d, kwadrat:%I64d\n", a, k/2, pom, pom2); if(pom == -1 || (pom2 == 1 && pom != 1 && pom != mod-1)) return -1; if(k&1) return (pom2*a)%mod; return pom2; } bool isPrime(long long l) { if(l <= 7) { if(l < 2) return 0; if(l == 2) return 1; return l&1; } return (MR(2, l, l) == 2) && (MR(3, l, l) == 3) && (MR(5, l, l) == 5) && (MR(7, l, l) == 7); } int main() { long long n, m = 0, dz = 1; scanf("%lld", &n); while(n > 9) { m += dz*(n%10); n /= 10; dz *= 10; if(10*m >= dz && isPrime(n) && isPrime(m)) { printf("TAK\n"); //cout << n << " " << m << endl; return 0; } } printf("NIE\n"); return 0; } |