pastebin

Paste Search Dynamic
Recent pastes
Fibonacci number is
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.*;
  4. class Nth_Fibonacci {
  5.  
  6.   static class Matrix {
  7.          /*data member*/  
  8.          public long[][] matrix;
  9.  
  10.  
  11.          /*Constructor*/
  12.          public Matrix(int n) {
  13.                 matrix=new long[n][n];                 
  14.          }
  15.  
  16.       /**
  17.        *  @param other Matrix
  18.        *  @param mod
  19.        *
  20.        * this method performs matrix multiplication of this.matrix
  21.        * and other.matrix and returns the product matrix
  22.        * */
  23.         public Matrix multiply(Matrix other,int mod) {
  24.  
  25.                Matrix product = new Matrix(matrix.length);
  26.  
  27.                for (int i = 0; i < matrix.length; i++) {
  28.                     for (int j = 0; j < matrix.length; j++) {
  29.                          for (int k = 0; k < matrix.length; k++) {
  30.                              product.matrix[i][k] = (product.matrix[i][k] + matrix[i][j] * other.matrix[j][k])%mod;
  31.                          }
  32.                     }
  33.                 }
  34.  
  35.                 return product;
  36.          }
  37.  
  38.       }
  39.  
  40.       /*binary exponentiation using matrices*/
  41.       public static Matrix exponentiation(Matrix m,biginteger n,int mod) {
  42.  
  43.             Matrix expo = new Matrix(m.matrix.length);
  44.  
  45.             for (int i = 0; i < m.matrix.length; i++) expo.matrix[i][i]=1;
  46.  
  47.             while(n.compareTo(biginteger.valueOf(0))>0) {
  48.  
  49.                     if(n.remainder(biginteger.valueOf(2)).compareTo(biginteger.valueOf(1)) == 0) expo = expo.multiply(m,mod);
  50.  
  51.                     m = m.multiply(m,mod);
  52.  
  53.                     n = n.divide(biginteger.valueOf(2));
  54.             }
  55.  
  56.             return expo;
  57.      }
  58.  
  59.      public static void main(string []args) throws ioexception {
  60.  
  61.            /*for taking input.*/
  62.            bufferedreader br = new bufferedreader(new inputstreamreader(system.in));
  63.  
  64.            /*because of constraints ,I read the number in string since it does not fit in long as well.*/
  65.            string s = br.readLine().trim();
  66.  
  67.            /*convert the string to bigInteger to be able to perform some arithmetic operations*/
  68.            biginteger n = new biginteger(s);
  69.  
  70.  
  71.            int mod = (int)1e9+7;
  72.  
  73.            Matrix A = new Matrix(2);
  74.            A.matrix[0][0] = 0;
  75.            A.matrix[0][1] = A.matrix[1][0] = A.matrix[1][1] = 1;
  76.  
  77.            Matrix ans = exponentiation(A,n,mod);
  78.  
  79.            int result = (int)(ans.matrix[0][1] % mod) ;
  80.  
  81.            system.out.println(n + "-th Fibonacci number is : " + result);
  82.    }
  83.  
  84. }
Parsed in 0.025 seconds