fork(1) download 
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. const long long MOD = 12345678901;
  5.  
  6. unsigned long long fibonacci(unsigned long long n)
  7. {
  8.     unsigned long long fib[2][2]= {{1,1},{1,0}},ret[2][2]= {{1,0},{0,1}},tmp[2][2]= {{0,0},{0,0}};
  9.     int i,j,k;
  10.     while(n)
  11.     {
  12.         if(n&1)
  13.         {
  14.             memset(tmp,0,sizeof tmp);
  15.             for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
  16.                         tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j])%MOD;
  17.             for(i=0; i<2; i++) for(j=0; j<2; j++) ret[i][j]=tmp[i][j];
  18.         }
  19.         memset(tmp,0,sizeof tmp);
  20.         for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
  21.                     tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j])%MOD;
  22.         for(i=0; i<2; i++) for(j=0; j<2; j++) fib[i][j]=tmp[i][j];
  23.         n/=2;
  24.     }
  25.     return (ret[0][1]);
  26. }
  27.  
  28. int main(){
  29.     int t;
  30.     scanf("%d",&t);
  31.     unsigned long long n;
  32.     while(t--){
  33.         scanf("%llu",&n);
  34.         n++;
  35.         printf("%llu\n", fibonacci(n));
  36.     }
  37.  
  38.     return 0;
  39. }
Success #stdin #stdout 0s 2160KB
comments (?)
stdin 
5
10
22
88
101
3
stdout 
89
28657
12305262156
1497829931
3
https://ideone.com/3TtE5m
problem NEWCURR, based on SPOJ submission 15002261 (C), 2015-08-28 15:43:22
language:
C (gcc 8.3)
created:
8 years ago
visibility:
secret

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!