import java.util.Scanner; public class fib { public static void main(String[] args) { long fc[][] = { {0, 1, 2}, {5, 8, 7}, {55, 89, 12}, {610, 987, 17}, {4181, 6765, 21}, {46368, 75025, 26}, {514229, 832040, 31}, {5702887, 9227465, 36}, {39088169, 63245986, 40}, {433494437, 701408733, 45}, {4807526976L, 7778742049L, 50}, {53316291173L, 86267571272L, 55}, {591286729879L, 956722026041L, 60}, {4052739537881L, 6557470319842L, 64}, {44945570212853L, 72723460248141L, 69}, {498454011879264L, 806515533049393L, 74}, {5527939700884757L, 8944394323791464L, 79}, {61305790721611591L, 99194853094755497L, 84} }; long[] cycles = new long[18]; cycles[0] = 60; cycles[1] = 300; cycles[2] = 1500; for (int i = 3; i < cycles.length; i++) { cycles[i] = 15 * (long) Math.pow(10, i); } Scanner scanner = new Scanner(System.in); String digits = scanner.nextLine(); scanner.close(); int n = digits.length(); long remainder = Long.valueOf(digits); boolean found = false; boolean localFound = false; MAIN: for (int i = 0; i <= n - 1; i++) { long f1 = fc[i][0]; long f2 = fc[i][1]; long startK = fc[i][2]; // position of fib long decimal = (int) Math.pow(10, i + 1); long localRemainder = remainder % decimal; LOCAL: for (long k = startK; k < cycles[i]; k++) { long f = (f1 + f2) % decimal; if (f == remainder) { System.out.println(k); found = true; break MAIN; } if (f == localRemainder) { localFound = true; break LOCAL; } f1 = f2; f2 = f; } if (!localFound) { break MAIN; } } if (!found) { System.out.println("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 | import java.util.Scanner; public class fib { public static void main(String[] args) { long fc[][] = { {0, 1, 2}, {5, 8, 7}, {55, 89, 12}, {610, 987, 17}, {4181, 6765, 21}, {46368, 75025, 26}, {514229, 832040, 31}, {5702887, 9227465, 36}, {39088169, 63245986, 40}, {433494437, 701408733, 45}, {4807526976L, 7778742049L, 50}, {53316291173L, 86267571272L, 55}, {591286729879L, 956722026041L, 60}, {4052739537881L, 6557470319842L, 64}, {44945570212853L, 72723460248141L, 69}, {498454011879264L, 806515533049393L, 74}, {5527939700884757L, 8944394323791464L, 79}, {61305790721611591L, 99194853094755497L, 84} }; long[] cycles = new long[18]; cycles[0] = 60; cycles[1] = 300; cycles[2] = 1500; for (int i = 3; i < cycles.length; i++) { cycles[i] = 15 * (long) Math.pow(10, i); } Scanner scanner = new Scanner(System.in); String digits = scanner.nextLine(); scanner.close(); int n = digits.length(); long remainder = Long.valueOf(digits); boolean found = false; boolean localFound = false; MAIN: for (int i = 0; i <= n - 1; i++) { long f1 = fc[i][0]; long f2 = fc[i][1]; long startK = fc[i][2]; // position of fib long decimal = (int) Math.pow(10, i + 1); long localRemainder = remainder % decimal; LOCAL: for (long k = startK; k < cycles[i]; k++) { long f = (f1 + f2) % decimal; if (f == remainder) { System.out.println(k); found = true; break MAIN; } if (f == localRemainder) { localFound = true; break LOCAL; } f1 = f2; f2 = f; } if (!localFound) { break MAIN; } } if (!found) { System.out.println("NIE"); } } } |