fork(5) download 
  1. class Fibonacci {
  2.  
  3.     static final int MOD=1000000007;
  4.  
  5.  
  6.     public static void main (String args[])
  7.     {
  8.         int a=3,b=4,n = 46;
  9.         System.out.println(solution(a,b,n));
  10.     }
  11.  
  12.     static int fib(int a,int b,int n)
  13.     {
  14.         int F[][] = new int[][]{{1,1},{1,0}};
  15.         if (n == 0)
  16.             return 0;
  17.         power(F, n-1);
  18.  
  19.         long ans=(((a%MOD)*(F[0][1]%MOD))%MOD+ (b%MOD)*(F[0][0]%MOD)%MOD)%MOD;
  20.  
  21.         return (int)(ans);
  22.     }
  23.  
  24.     /* Helper function that multiplies 2 matrices F and M of size 2*2, and
  25.     puts the multiplication result back to F[][] */
  26.     static void multiply(int F[][], int M[][])
  27.     {/*
  28.         int x =  (((F[0][0]%MOD)*(M[0][0]%MOD)%MOD) + (((F[0][1]%MOD)*(M[1][0]%MOD))%MOD))%MOD;
  29.         int y=(((F[0][0]%MOD)*(M[0][1]%MOD)%MOD) + (((F[0][1]%MOD)*(M[1][1]%MOD))%MOD))%MOD;
  30.         int z=(((F[1][0]%MOD)*(M[0][0]%MOD)%MOD) + (((F[1][1]%MOD)*(M[1][0]%MOD))%MOD))%MOD;
  31.         int w=(((F[1][0]%MOD)*(M[0][1]%MOD)%MOD) + (((F[1][1]%MOD)*(M[1][1]%MOD))%MOD))%MOD;
  32.      */
  33.         int x =  ((F[0][0]*M[0][0])%MOD + (F[0][1]*M[1][0])%MOD)%MOD;
  34.         int y =  ((F[0][0]*M[0][1])%MOD + (F[0][1]*M[1][1])%MOD)%MOD;
  35.         int z =  ((F[1][0]*M[0][0])%MOD + (F[1][1]*M[1][0])%MOD)%MOD;
  36.         int w =  ((F[1][0]*M[0][1])%MOD + (F[1][1]*M[1][1])%MOD)%MOD;
  37.  
  38.         F[0][0] = x;
  39.         F[0][1] = y;
  40.         F[1][0] = z;
  41.         F[1][1] = w;
  42.     }
  43.  
  44.     /* Helper function that calculates F[][] raise to the power n and puts the
  45.     result in F[][]
  46.     Note that this function is designed only for fib() and won't work as general
  47.     power function */
  48.     static void power(int F[][], int n)
  49.     {
  50.         int i;
  51.         int M[][] = new int[][]{{1,1},{1,0}};
  52.  
  53.         // n - 1 times multiply the matrix to {{1,0},{0,1}}
  54.         for (i = 2; i <= n; i++)
  55.             multiply(F, M);
  56.     }
  57.  
  58.     /* Driver program to test above function */
  59.  
  60.  
  61.  
  62.     public static int solution(int A,int B,int N){
  63.             return fib(A,B,N);
  64.     }
  65. }
Success #stdin #stdout 0.05s 711168KB
comments (?)
stdin 
Standard input is empty
stdout 
-545010223
https://ideone.com/mmGyDZ
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!