Ideone.com

fork download

#include <iostream>
using namespace std;
 
long long multiply(long long a, long long b, long long M) {
    long long res = 0;
    long long d = a;
 
    while (b > 0) {
        if (b & 1) {
            res = (res + d) % M;
        }
        b /= 2;
        d = (d + d) % M;
    }
    return res;
}
 
void fast_fib(long long n,long long ans[], long long mod){
    if (n == 0) {
        ans[0] = 0;
        ans[1] = 1;
        return;
    }
    fast_fib(n/2, ans, mod);
    long long a = ans[0];             /* F(n) */
    long long b = ans[1];             /* F(n+1) */
    long long c = (((2*b) % mod) + mod - a) % mod;
    c = multiply(a, c, mod);      /* F(2n) */
    long long d = (multiply(a, a, mod) + multiply(b, b, mod)) % mod;  /* F(2n + 1) */
    if (n % 2 == 0) {
        ans[0] = c;
        ans[1] = d;
    }
    else {
        ans[0] = d;
        ans[1] = (c+d) % mod;
    }
}
 
int main() {
  int T = 1000;
  while (T--) {
    long long n;
    long long mod;
    scanf("%lld %lld", &n, &mod);
    long long ans[2] = {0};
    fast_fib(n, ans, mod);
    printf("%lld\n", ans[0]);
  }
  return 0;
}

Success #stdin #stdout 0s 16064KB

stdin

1 1000000007
2 1000000007
3 1000000007
4 1000000007
5 1000000007
6 1000000007
7 1000000007
98 1000000007
99 1000000007
100 1000000007

stdout

Discover > Sphere Engine API

Discover > IDE Widget

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language