fork(4) download 
  1. #include <iostream>
  2. #include <deque>
  3. #include <string>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ull;
  9.  
  10. namespace
  11. {
  12. typedef deque<ull> bigint;
  13. const ull base = 9;
  14. const ull base10 = pow(10, base);
  15.  
  16. class BigInteger
  17. {
  18. public:
  19.     static void print(bigint a)
  20.     {
  21.         for (ull i = 0; i < a.size(); ++i)
  22.         {
  23.             int ndigits = a[i] > 0 ? (int) log10 ((double) a[i]) + 1 : 1;
  24.             if (ndigits < base && i != 0)
  25.             {
  26.                 for (int j = 0; j < base - ndigits; ++j)
  27.                     cout << 0;
  28.             }
  29.             cout << a[i];
  30.         }
  31.         cout << endl;
  32.     }
  33.  
  34.     static bigint str_to_bigint(string str)
  35.     {
  36.         bigint res;
  37.         for (ull i = 0; i < str.length(); i += base)
  38.         {
  39.             ull shift = i + base;
  40.             if (shift > str.length()) shift -= shift - str.length();
  41.             string curr_digit_str(str.end() - shift, str.end() - i);
  42.             res.push_front(atoi(curr_digit_str.c_str()));
  43.         }
  44.         return res;
  45.     }
  46.  
  47.     static bigint mul(bigint a, bigint b)
  48.     {
  49.         ull cnt = 0;
  50.         bigint res;
  51.         for (ull i = b.size() - 1; i >= 0; --i)
  52.         {
  53.             bigint r = mul(a, b[i]);
  54.             for (ull i = 0; i < cnt; ++i) { r.push_back(0); }
  55.             res = add(res, r);
  56.             cnt++;
  57.         }
  58.  
  59.         return res;
  60.     }
  61.  
  62.     static bigint mul(bigint a, ull b)
  63.     {
  64.         bigint res;
  65.         ull mem = 0;
  66.         for (ull i = a.size() - 1; i >= 0; --i)
  67.         {
  68.             ull r = a[i] * b + mem;
  69.             res.push_front(r % base10);
  70.             mem = (r - r % base10) / base10;
  71.         }
  72.         if (mem != 0) res.push_front(mem); 
  73.  
  74.         return res;
  75.     }
  76.  
  77.     static bigint add(bigint a, bigint b)
  78.     {
  79.         if (a.size() < b.size()) while (a.size() != b.size()) { a.push_front(0); }
  80.         else if (a.size() > b.size()) while (a.size() != b.size()) { b.push_front(0); }
  81.  
  82.         bigint res;
  83.         ull mem = 0;
  84.         for (ull i = a.size() - 1; i >= 0; --i)
  85.         {
  86.             ull r = a[i] + b[i] + mem;
  87.             res.push_front(r % base10);
  88.             mem = (r - r % base10) / base10;
  89.         }
  90.         if (mem != 0) res.push_front(mem);
  91.  
  92.         return res;
  93.     }
  94. };
  95.  
  96. }
  97.  
  98. ull a, b;
  99. bigint biga, bigb;
  100.  
  101. bigint modified_fib(ull n)
  102. {
  103.     for (int i = 0; i < n - 2; ++i)
  104.     {
  105.         bigint r = BigInteger::add(BigInteger::mul(bigb, bigb), biga);
  106.         biga = bigb;
  107.         bigb = r;
  108.     }
  109.  
  110.     return bigb;
  111. }
  112.  
  113. int main()
  114. {
  115.     cin >> a >> b;
  116.  
  117.     biga.push_back(a);
  118.     bigb.push_back(b);
  119.  
  120.     ull N;
  121.     cin >> N;
  122.  
  123.     bigint res = modified_fib(N);
  124.  
  125.     BigInteger::print(res);
  126.  
  127.     return 0;
  128. }
Success #stdin #stdout 0s 3484KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/or4YD8
language:
C++14 (gcc 8.3)
created:
8 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!