Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.math.BigInteger;
- import java.util.Scanner;
- public class FastFib {
- public static void main(String[] args) {
- Scanner gwS = new Scanner(System.in);
- System.out.println(ah3(new BigInteger[][]{{BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ZERO}}, gwS.nextInt() - 1)[0][0]);
- }
- private static BigInteger[][]bsg(BigInteger[][] dpl, BigInteger[][] zuy) {
- return new BigInteger[][]{{dpl[0][0].multiply(zuy[0][0]).add(dpl[0][1].multiply(zuy[1][0])), dpl[0][0].multiply(zuy[0][1]).add(dpl[0][1].multiply(zuy[1][1]))}, {dpl[1][0].multiply(zuy[0][0]).add(dpl[1][1].multiply(zuy[1][0])), dpl[1][0].multiply(zuy[0][1]).add(dpl[1][1].multiply(zuy[1][1]))},};
- }
- private static BigInteger[][]ah3(BigInteger[][] nkG, int hx3) {
- if (hx3 == 0) {return new BigInteger[][]{{BigInteger.ONE, BigInteger.ZERO}, {BigInteger.ZERO, BigInteger.ONE}}; } else if (hx3 % 2 == 0) { return ah3(bsg(nkG, nkG), hx3 / 2); } else { return bsg(ah3(nkG, hx3 - 1), nkG); }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement