import javafx.util.Pair; import java.math.BigInteger; import java.util.*; public class fib { private final BigInteger MOD = new BigInteger("1000000000000000000"); private class Matrix { BigInteger a, b, c, d; BigInteger count; Matrix() { } Matrix(BigInteger a, BigInteger b, BigInteger c, BigInteger d) { this.a = a; this.b = b; this.c = c; this.d = d; } @Override public boolean equals(Object obj) { Matrix m = (Matrix) obj; return m.a.equals(this.a) && m.b.equals(this.b) && m.c.equals(this.c) && m.d.equals(this.d); } @Override public int hashCode() { return Objects.hash(a, b, c, d); } @Override public String toString() { return a + ", " + b + ", " + c + ", " + d; } } private Matrix times(Matrix m1, Matrix m2) { Matrix res = new Matrix(); res.a = ((m1.a.multiply(m2.a)).add(m1.b.multiply(m2.c))).mod(MOD); res.b = ((m1.a.multiply(m2.b)).add(m1.b.multiply(m2.d))).mod(MOD); res.c = ((m1.c.multiply(m2.a)).add(m1.d.multiply(m2.c))).mod(MOD); res.d = ((m1.c.multiply(m2.b)).add(m1.d.multiply(m2.d))).mod(MOD); return res; } HashMap<Pair<Long, Matrix>, Matrix> cache = new HashMap<Pair<Long, Matrix>, Matrix>(); private Matrix pow(long k, Matrix m) { if (cache.containsKey(new Pair<Long, Matrix>(k, m)) && k < 1000000){ return cache.get(new Pair<Long, Matrix>(k, m)); } if (k == 0) { return new Matrix(new BigInteger("1"), new BigInteger("0"), new BigInteger("0"), new BigInteger("1")); } if (k <= 1) { return m; } if (k % 2 == 0) { return pow(k / 2, times(m, m)); } else { Matrix mat =times(m, pow(k / 2, times(m, m))); cache.put(new Pair<Long, Matrix>(k, m), mat); return mat; } } private void testMatrix() { Matrix m = new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("1"), new BigInteger("0")); Matrix res = pow(12, m); assert (res.a.longValue() == 233); assert (res.b.longValue() == 144); assert (res.c.longValue() == 144); assert (res.d.longValue() == 89); } private Matrix getFib(long k) { Matrix zero = new Matrix(new BigInteger("0"), new BigInteger("0"), new BigInteger("0"), new BigInteger("0")); Matrix one = new Matrix(new BigInteger("1"), new BigInteger("0"), new BigInteger("0"), new BigInteger("0")); Matrix two = new Matrix(new BigInteger("1"), new BigInteger("0"), new BigInteger("0"), new BigInteger("0")); if (k == 0) return zero; if (k == 1) return one; if (k == 2) return two; Matrix start = new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("0"), new BigInteger("0")); Matrix mul = new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("1"), new BigInteger("0")); return times(mul, pow(k - 2, mul)); } private BigInteger getMod(String line) { BigInteger mod = new BigInteger("1" + line); BigInteger mod2 = new BigInteger(line); return mod.subtract(mod2); } private void solve(String line) { //testMatrix(); BigInteger modul = getMod(line); BigInteger nr = new BigInteger(line); BigInteger m = new BigInteger("10"); BigInteger cycle = new BigInteger("15"); List<Matrix> next = new LinkedList<Matrix>(); for (long k = 1; k < 200; k++) { Matrix mat = getFib(k); mat.count = new BigInteger(String.valueOf(k)); if (mat.a.mod(m).equals(nr.mod(m))) { next.add(mat); } } while (modul.compareTo(m) >= 0) { List<Matrix> current = next; next = new LinkedList<Matrix>(); for (Matrix matrix : current) { for (long i = 0; i <= 10; i++) { Matrix res = times(matrix, pow(cycle.longValue() * i, new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("1"), new BigInteger("0")))); res.count = matrix.count.add(cycle.multiply(new BigInteger(String.valueOf(i)))); if (res.a.mod(m).equals(nr.mod(m))) { next.add(res); if (modul.compareTo(m) == 0) { System.out.print(res.count); return; } } } } cycle = cycle.multiply(new BigInteger("10")); m = m.multiply(new BigInteger("10")); } System.out.println("NIE"); } public static void main(String args[]) { fib a = new fib(); Scanner scanner = new Scanner(System.in); //while (true) { String line = scanner.nextLine(); a.solve(line); //} } }
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 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 | import javafx.util.Pair; import java.math.BigInteger; import java.util.*; public class fib { private final BigInteger MOD = new BigInteger("1000000000000000000"); private class Matrix { BigInteger a, b, c, d; BigInteger count; Matrix() { } Matrix(BigInteger a, BigInteger b, BigInteger c, BigInteger d) { this.a = a; this.b = b; this.c = c; this.d = d; } @Override public boolean equals(Object obj) { Matrix m = (Matrix) obj; return m.a.equals(this.a) && m.b.equals(this.b) && m.c.equals(this.c) && m.d.equals(this.d); } @Override public int hashCode() { return Objects.hash(a, b, c, d); } @Override public String toString() { return a + ", " + b + ", " + c + ", " + d; } } private Matrix times(Matrix m1, Matrix m2) { Matrix res = new Matrix(); res.a = ((m1.a.multiply(m2.a)).add(m1.b.multiply(m2.c))).mod(MOD); res.b = ((m1.a.multiply(m2.b)).add(m1.b.multiply(m2.d))).mod(MOD); res.c = ((m1.c.multiply(m2.a)).add(m1.d.multiply(m2.c))).mod(MOD); res.d = ((m1.c.multiply(m2.b)).add(m1.d.multiply(m2.d))).mod(MOD); return res; } HashMap<Pair<Long, Matrix>, Matrix> cache = new HashMap<Pair<Long, Matrix>, Matrix>(); private Matrix pow(long k, Matrix m) { if (cache.containsKey(new Pair<Long, Matrix>(k, m)) && k < 1000000){ return cache.get(new Pair<Long, Matrix>(k, m)); } if (k == 0) { return new Matrix(new BigInteger("1"), new BigInteger("0"), new BigInteger("0"), new BigInteger("1")); } if (k <= 1) { return m; } if (k % 2 == 0) { return pow(k / 2, times(m, m)); } else { Matrix mat =times(m, pow(k / 2, times(m, m))); cache.put(new Pair<Long, Matrix>(k, m), mat); return mat; } } private void testMatrix() { Matrix m = new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("1"), new BigInteger("0")); Matrix res = pow(12, m); assert (res.a.longValue() == 233); assert (res.b.longValue() == 144); assert (res.c.longValue() == 144); assert (res.d.longValue() == 89); } private Matrix getFib(long k) { Matrix zero = new Matrix(new BigInteger("0"), new BigInteger("0"), new BigInteger("0"), new BigInteger("0")); Matrix one = new Matrix(new BigInteger("1"), new BigInteger("0"), new BigInteger("0"), new BigInteger("0")); Matrix two = new Matrix(new BigInteger("1"), new BigInteger("0"), new BigInteger("0"), new BigInteger("0")); if (k == 0) return zero; if (k == 1) return one; if (k == 2) return two; Matrix start = new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("0"), new BigInteger("0")); Matrix mul = new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("1"), new BigInteger("0")); return times(mul, pow(k - 2, mul)); } private BigInteger getMod(String line) { BigInteger mod = new BigInteger("1" + line); BigInteger mod2 = new BigInteger(line); return mod.subtract(mod2); } private void solve(String line) { //testMatrix(); BigInteger modul = getMod(line); BigInteger nr = new BigInteger(line); BigInteger m = new BigInteger("10"); BigInteger cycle = new BigInteger("15"); List<Matrix> next = new LinkedList<Matrix>(); for (long k = 1; k < 200; k++) { Matrix mat = getFib(k); mat.count = new BigInteger(String.valueOf(k)); if (mat.a.mod(m).equals(nr.mod(m))) { next.add(mat); } } while (modul.compareTo(m) >= 0) { List<Matrix> current = next; next = new LinkedList<Matrix>(); for (Matrix matrix : current) { for (long i = 0; i <= 10; i++) { Matrix res = times(matrix, pow(cycle.longValue() * i, new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("1"), new BigInteger("0")))); res.count = matrix.count.add(cycle.multiply(new BigInteger(String.valueOf(i)))); if (res.a.mod(m).equals(nr.mod(m))) { next.add(res); if (modul.compareTo(m) == 0) { System.out.print(res.count); return; } } } } cycle = cycle.multiply(new BigInteger("10")); m = m.multiply(new BigInteger("10")); } System.out.println("NIE"); } public static void main(String args[]) { fib a = new fib(); Scanner scanner = new Scanner(System.in); //while (true) { String line = scanner.nextLine(); a.solve(line); //} } } |