|
|
back to boardAC Java 1.8 0.078s 388 KB (top solution, 10th place) Posted by esbybb 6 Aug 2015 10:52 //package timus; import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.Reader; import java.math.BigInteger; import java.util.StringTokenizer; public class p1133 { public static void main(String[] args) throws FileNotFoundException { InputStream is = System.in; // is = new FileInputStream(new File("A.txt")); FastScanner sc = new FastScanner(new InputStreamReader(is)); int i = sc.nextInt(); int Fi = sc.nextInt(); int j = sc.nextInt(); int Fj = sc.nextInt(); int n = sc.nextInt(); if (i>j) { int reg = i; i = j; j = reg; reg = Fi; Fi = Fj; Fj = reg; } BigInteger f1 = fastFibonacciDoubling(j-i-1); BigInteger f2 = fastFibonacciDoubling(j-i); BigInteger pr = BigInteger.valueOf(Fj); BigInteger FI = BigInteger.valueOf(Fi); pr = pr.subtract(f2.multiply(FI)); pr = pr.divide(f1); int diff = 0; if (n>i) { diff = n - i; } else { diff = i - n; } BigInteger a = fastFibonacciDoubling(diff).multiply(FI); BigInteger b = fastFibonacciDoubling(diff-1).multiply(pr); System.out.println(a.add(b)); } private static BigInteger fastFibonacciDoubling(int n) { n++; BigInteger a = BigInteger.ZERO; BigInteger b = BigInteger.ONE; int m = 0; for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) { BigInteger d = multiply(a, b.shiftLeft(1).subtract(a)); BigInteger e = multiply(a, a).add(multiply(b, b)); a = d; b = e; m *= 2; if (((n >>> i) & 1) != 0) { BigInteger c = a.add(b); a = b; b = c; m++; } } return a; } private static BigInteger multiply(BigInteger x, BigInteger y) { return x.multiply(y); }
static class FastScanner { BufferedReader br; StringTokenizer st; FastScanner(Reader in) { br = new BufferedReader(in); } String next() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } } } |
|
|