fork(4) download
copy 
  1. /*
  2.   Copyright 2011 Marek "p2004a" Rusinowski
  3.   nth element of Fibonacci sequence (logarithmic)
  4. */
  5. #include <cstdio>
  6.  
  7. typedef unsigned long long int llu;
  8.  
  9. llu *multiply(llu *l, llu *r, llu *res, llu c) {
  10.   res[0] = ((l[1] * r[2]) % c + (l[0] * r[0]) % c) % c;
  11.   res[1] = ((l[1] * r[3]) % c + (l[0] * r[1]) % c) % c;
  12.   res[2] = ((l[3] * r[2]) % c + (l[2] * r[0]) % c) % c;
  13.   res[3] = ((l[3] * r[3]) % c + (l[2] * r[1]) % c) % c;
  14.   return res;
  15. }
  16.  
  17. int fib(int n, int c) {
  18.   llu *d = new llu [4], *res = new llu [4], *tmp1 = new llu [4], *tmp2;
  19.   d[0] = 1; d[1] = 1;
  20.   d[2] = 1; d[3] = 0;
  21.   res[0] = 1; res[1] = 0;
  22.   res[2] = 0; res[3] = 1;
  23.   while (n) {
  24.     if (n & 1) {
  25.       tmp2 = res;
  26.       res = multiply(res, d, tmp1, c);
  27.       tmp1 = tmp2;
  28.     }
  29.     tmp2 = d;
  30.     d = multiply(d, d, tmp1, c);
  31.     tmp1 = tmp2;
  32.     n >>= 1;
  33.   }
  34.   llu out = res[0];
  35.   delete d;
  36.   delete res;
  37.   delete tmp1;
  38.   return out;
  39. }
  40.  
  41. int main() {
  42.   int a, c;
  43.   scanf("%d %d", &a, &c);
  44.   printf("%d\n", fib(a, c));
  45.   return 0;
  46. }
  47.  
stdin
copy 
6 10000
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
stdout
copy 
13
https://ideone.com/bJTKJ
language:
C++ (gcc 8.3)
created:
12 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!