pastebin

Paste Search Dynamic
Recent pastes
fib
  1. #include <bits/stdc++.h>
  2. #define MOD 1000000007
  3. using namespace std;
  4.  
  5.  
  6. pair<unsigned long long int, unsigned long long int> fib(unsigned long long input)
  7. {
  8.     if (input == 0)
  9.         return {0,1};
  10.     pair<unsigned long long, unsigned long long> buff = fib(input/2);
  11.     unsigned long long c = (buff.first * ((((buff.second*2)%MOD)-buff.first)%MOD))%MOD;
  12.     unsigned long long d = ((buff.first*buff.first)%MOD + (buff.second*buff.second)%MOD)%MOD;
  13.     if (input % 2 == 0)
  14.     {
  15.         return {c,d};
  16.     }
  17.     else
  18.     {
  19.         return {d,c+d};
  20.     }
  21. }
  22.  
  23.  
  24. int main()
  25. {
  26.     ios::sync_with_stdio(0);
  27.     cin.tie(0);
  28.  
  29.     unsigned long long input;
  30.     while(cin >> input)
  31.     {
  32.        cout << fib(input+2).first << "n";
  33.     }
  34. }
Parsed in 0.011 seconds