import java.math.*; import java.util.*; public class fib { static BigInteger[] dec = new BigInteger[50]; static void calc_dec() { dec[0] = BigInteger.valueOf(1); for (int i = 1; i < 50; ++i) dec[i] = dec[i - 1].multiply(BigInteger.valueOf(10)); } static BigInteger period(int d) { if (d == 1) return BigInteger.valueOf(60); if (d == 2) return BigInteger.valueOf(300); return dec[d - 1].multiply(BigInteger.valueOf(15)); } static BigInteger[] mult(BigInteger[] a, BigInteger[] b, BigInteger mod) { BigInteger[] r = new BigInteger[4]; r[0] = a[0].multiply(b[0]).mod(mod).add(a[1].multiply(b[2]).mod(mod)).mod(mod); r[1] = a[0].multiply(b[1]).mod(mod).add(a[1].multiply(b[3]).mod(mod)).mod(mod); r[2] = a[2].multiply(b[0]).mod(mod).add(a[3].multiply(b[2]).mod(mod)).mod(mod); r[3] = a[2].multiply(b[1]).mod(mod).add(a[3].multiply(b[3]).mod(mod)).mod(mod); return r; } static BigInteger calc_fib(BigInteger k, BigInteger mod) { BigInteger r[] = new BigInteger[4]; r[0] = BigInteger.valueOf(1); r[2] = BigInteger.valueOf(1); r[1] = BigInteger.valueOf(0); r[3] = BigInteger.valueOf(0); BigInteger x[] = new BigInteger[4]; x[0] = BigInteger.valueOf(1); x[2] = BigInteger.valueOf(1); x[1] = BigInteger.valueOf(1); x[3] = BigInteger.valueOf(0); while (k.compareTo(BigInteger.valueOf(0)) != 0) { if (k.mod(BigInteger.valueOf(2)).intValue() == 1) r = mult(r, x, mod); x = mult(x, x, mod); k = k.divide(BigInteger.valueOf(2)); } return r[1]; } static BigInteger debug; static BigInteger res; static final boolean do_debug = false; static boolean dfs(BigInteger target, BigInteger cur, int matched, int total, BigInteger pos) { if (matched == total) { res = pos; if (false) debug = calc_fib(pos, dec[50 - 1]); return true; } BigInteger prev = period(matched), next = period(matched + 1); BigInteger mod = dec[matched + 1]; cur = target.mod(mod); for (BigInteger t = pos; t.compareTo(next) < 0; t = t.add(prev)) { BigInteger fib = calc_fib(t, mod); if (fib.compareTo(cur) == 0) if (dfs(target, cur, matched + 1, total, t)) return true; } return false; } static boolean try_solve(String s) { int total = s.length(); BigInteger target = new BigInteger(s); for (int i = 0; i < 60; ++i) { BigInteger fib = calc_fib(BigInteger.valueOf(i), BigInteger.valueOf(10)); if (fib.intValue() == target.mod(BigInteger.valueOf(10)).intValue()) if (dfs(target, fib, 1, total, BigInteger.valueOf(i))) return true; } return false; } static final int tests = 1; static void success() { if (tests == 1) { if (do_debug) System.out.println(debug); System.out.println(res); } else System.out.println("TAK"); } public static void main(String[] args) { calc_dec(); Scanner scanner = new Scanner(System.in); for (int q = 0; q < tests; ++q) { String s = scanner.nextLine(); if (s.charAt(0) == '0') { if (!try_solve(s)) System.out.println("NIE"); else { for (int i = 1; ; ++i) { if (try_solve(i + s)) { success(); break; } } } } else { if (!try_solve(s)) System.out.println("NIE"); else success(); } } } }
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 | import java.math.*; import java.util.*; public class fib { static BigInteger[] dec = new BigInteger[50]; static void calc_dec() { dec[0] = BigInteger.valueOf(1); for (int i = 1; i < 50; ++i) dec[i] = dec[i - 1].multiply(BigInteger.valueOf(10)); } static BigInteger period(int d) { if (d == 1) return BigInteger.valueOf(60); if (d == 2) return BigInteger.valueOf(300); return dec[d - 1].multiply(BigInteger.valueOf(15)); } static BigInteger[] mult(BigInteger[] a, BigInteger[] b, BigInteger mod) { BigInteger[] r = new BigInteger[4]; r[0] = a[0].multiply(b[0]).mod(mod).add(a[1].multiply(b[2]).mod(mod)).mod(mod); r[1] = a[0].multiply(b[1]).mod(mod).add(a[1].multiply(b[3]).mod(mod)).mod(mod); r[2] = a[2].multiply(b[0]).mod(mod).add(a[3].multiply(b[2]).mod(mod)).mod(mod); r[3] = a[2].multiply(b[1]).mod(mod).add(a[3].multiply(b[3]).mod(mod)).mod(mod); return r; } static BigInteger calc_fib(BigInteger k, BigInteger mod) { BigInteger r[] = new BigInteger[4]; r[0] = BigInteger.valueOf(1); r[2] = BigInteger.valueOf(1); r[1] = BigInteger.valueOf(0); r[3] = BigInteger.valueOf(0); BigInteger x[] = new BigInteger[4]; x[0] = BigInteger.valueOf(1); x[2] = BigInteger.valueOf(1); x[1] = BigInteger.valueOf(1); x[3] = BigInteger.valueOf(0); while (k.compareTo(BigInteger.valueOf(0)) != 0) { if (k.mod(BigInteger.valueOf(2)).intValue() == 1) r = mult(r, x, mod); x = mult(x, x, mod); k = k.divide(BigInteger.valueOf(2)); } return r[1]; } static BigInteger debug; static BigInteger res; static final boolean do_debug = false; static boolean dfs(BigInteger target, BigInteger cur, int matched, int total, BigInteger pos) { if (matched == total) { res = pos; if (false) debug = calc_fib(pos, dec[50 - 1]); return true; } BigInteger prev = period(matched), next = period(matched + 1); BigInteger mod = dec[matched + 1]; cur = target.mod(mod); for (BigInteger t = pos; t.compareTo(next) < 0; t = t.add(prev)) { BigInteger fib = calc_fib(t, mod); if (fib.compareTo(cur) == 0) if (dfs(target, cur, matched + 1, total, t)) return true; } return false; } static boolean try_solve(String s) { int total = s.length(); BigInteger target = new BigInteger(s); for (int i = 0; i < 60; ++i) { BigInteger fib = calc_fib(BigInteger.valueOf(i), BigInteger.valueOf(10)); if (fib.intValue() == target.mod(BigInteger.valueOf(10)).intValue()) if (dfs(target, fib, 1, total, BigInteger.valueOf(i))) return true; } return false; } static final int tests = 1; static void success() { if (tests == 1) { if (do_debug) System.out.println(debug); System.out.println(res); } else System.out.println("TAK"); } public static void main(String[] args) { calc_dec(); Scanner scanner = new Scanner(System.in); for (int q = 0; q < tests; ++q) { String s = scanner.nextLine(); if (s.charAt(0) == '0') { if (!try_solve(s)) System.out.println("NIE"); else { for (int i = 1; ; ++i) { if (try_solve(i + s)) { success(); break; } } } } else { if (!try_solve(s)) System.out.println("NIE"); else success(); } } } } |