import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class fib { public static final BigInteger MOD = new BigInteger("1000000000000000000"); public static final BigInteger ZERO = BigInteger.ZERO; public static final BigInteger ONE = BigInteger.ONE; public static final BigInteger FIVE = new BigInteger("5"); public static final BigInteger TEN = new BigInteger("10"); public static final BigInteger FIRST_19_DIGITS_FIB = new BigInteger("88"); private static Map<BigInteger, BigInteger> fibs = new HashMap<>(); // F(2n-1) = F(n-1)^2 + F(n)^2 // F(2n) = ( 2 F(n-1) + F(n) ) F(n) private static String fibonacci(BigInteger fi) { fibs.clear(); fibs.put(ZERO, ZERO); fibs.put(ONE, ONE); BigInteger fib2 = fib2(fi); if (fi.compareTo(FIRST_19_DIGITS_FIB) == -1) { return fib2.toString(); } String fib2string = fib2.toString(); return ("000000000000000000" + fib2string).substring(fib2string.length()); } private static BigInteger fib2(BigInteger fi) { if (fibs.containsKey(fi)) { return fibs.get(fi); } BigInteger value; if (fi.testBit(0)) { BigInteger n = fi.add(ONE).shiftRight(1); BigInteger fibn = fib2(n); BigInteger fibn2 = fibn.multiply(fibn); BigInteger fibn1 = fib2(n.subtract(ONE)); BigInteger fibn12 = fibn1.multiply(fibn1); value = fibn2.add(fibn12); } else { BigInteger n = fi.shiftRight(1); BigInteger fibn = fib2(n); value = fib2(n.subtract(ONE)).shiftLeft(1).add(fibn).multiply(fibn); } value = value.mod(MOD); fibs.put(fi, value); return value; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String numberString = in.readLine(); in.close(); List<BigInteger> suspects = new ArrayList<>(); char lastChar = numberString.charAt(numberString.length() - 1); for (Integer fi = 0; fi < 60; fi++) { BigInteger fibi = new BigInteger(fi.toString()); String f = fibonacci(fibi); char fLastChar = f.charAt(f.length() - 1); if (lastChar == fLastChar) { suspects.add(fibi); } } BigInteger cycle = new BigInteger("60"); for (int i = 2; i <= numberString.length(); i++) { char neededChar = numberString.charAt(numberString.length() - i); List<BigInteger> newSuspects = new ArrayList<>(); for (BigInteger fibi : suspects) { BigInteger next = fibi; int maxA = i < 4 ? 5 : 10; for (int a = 0; a < maxA; a++) { String f = fibonacci(next); if (f.length() >= i) { char fChar = f.charAt(f.length() - i); if (neededChar == fChar) { newSuspects.add(next); } } else { newSuspects.add(next); } next = next.add(cycle); } } if (i < 4) cycle = cycle.multiply(FIVE); else cycle = cycle.multiply(TEN); suspects = newSuspects; } BigInteger answer = null; for (BigInteger fibi : suspects) { if (fibonacci(fibi).endsWith(numberString)) { answer = fibi; break; } } if (answer == null) { System.out.println("NIE"); } else { System.out.println(answer); } } }
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.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class fib { public static final BigInteger MOD = new BigInteger("1000000000000000000"); public static final BigInteger ZERO = BigInteger.ZERO; public static final BigInteger ONE = BigInteger.ONE; public static final BigInteger FIVE = new BigInteger("5"); public static final BigInteger TEN = new BigInteger("10"); public static final BigInteger FIRST_19_DIGITS_FIB = new BigInteger("88"); private static Map<BigInteger, BigInteger> fibs = new HashMap<>(); // F(2n-1) = F(n-1)^2 + F(n)^2 // F(2n) = ( 2 F(n-1) + F(n) ) F(n) private static String fibonacci(BigInteger fi) { fibs.clear(); fibs.put(ZERO, ZERO); fibs.put(ONE, ONE); BigInteger fib2 = fib2(fi); if (fi.compareTo(FIRST_19_DIGITS_FIB) == -1) { return fib2.toString(); } String fib2string = fib2.toString(); return ("000000000000000000" + fib2string).substring(fib2string.length()); } private static BigInteger fib2(BigInteger fi) { if (fibs.containsKey(fi)) { return fibs.get(fi); } BigInteger value; if (fi.testBit(0)) { BigInteger n = fi.add(ONE).shiftRight(1); BigInteger fibn = fib2(n); BigInteger fibn2 = fibn.multiply(fibn); BigInteger fibn1 = fib2(n.subtract(ONE)); BigInteger fibn12 = fibn1.multiply(fibn1); value = fibn2.add(fibn12); } else { BigInteger n = fi.shiftRight(1); BigInteger fibn = fib2(n); value = fib2(n.subtract(ONE)).shiftLeft(1).add(fibn).multiply(fibn); } value = value.mod(MOD); fibs.put(fi, value); return value; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String numberString = in.readLine(); in.close(); List<BigInteger> suspects = new ArrayList<>(); char lastChar = numberString.charAt(numberString.length() - 1); for (Integer fi = 0; fi < 60; fi++) { BigInteger fibi = new BigInteger(fi.toString()); String f = fibonacci(fibi); char fLastChar = f.charAt(f.length() - 1); if (lastChar == fLastChar) { suspects.add(fibi); } } BigInteger cycle = new BigInteger("60"); for (int i = 2; i <= numberString.length(); i++) { char neededChar = numberString.charAt(numberString.length() - i); List<BigInteger> newSuspects = new ArrayList<>(); for (BigInteger fibi : suspects) { BigInteger next = fibi; int maxA = i < 4 ? 5 : 10; for (int a = 0; a < maxA; a++) { String f = fibonacci(next); if (f.length() >= i) { char fChar = f.charAt(f.length() - i); if (neededChar == fChar) { newSuspects.add(next); } } else { newSuspects.add(next); } next = next.add(cycle); } } if (i < 4) cycle = cycle.multiply(FIVE); else cycle = cycle.multiply(TEN); suspects = newSuspects; } BigInteger answer = null; for (BigInteger fibi : suspects) { if (fibonacci(fibi).endsWith(numberString)) { answer = fibi; break; } } if (answer == null) { System.out.println("NIE"); } else { System.out.println(answer); } } } |