fork(6) download
copy 
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. using Long = unsigned long long;
  8.  
  9. struct XLong {
  10.     static Long const F=100000000ULL;
  11.     vector<Long> d;
  12.     XLong()=default;
  13.     XLong(vector<Long>&& i): d{move(i)} {}
  14.     XLong(Long i): d{i} {}
  15.  
  16.     //make all array elements in range of 8 digits
  17.     void inRange() {
  18.         Long rem=0;
  19.         for (Long& dp: d) {
  20.             dp += rem;
  21.             rem = dp/F;
  22.             dp %= F;
  23.         }
  24.         while(d.back()==0)
  25.             d.pop_back();
  26.     }
  27.     //plus
  28.     XLong operator + (XLong const& r) const {
  29.         size_t m= 1 + max(d.size(), r.d.size());
  30.         XLong ret{vector<Long>(m, 0)};
  31.         for(size_t i=0; i<d.size(); i++)
  32.             ret.d[i] = d[i];
  33.         for(size_t i=0; i<r.d.size(); i++)
  34.             ret.d[i] += r.d[i];
  35.         ret.inRange();
  36.         return ret;
  37.     }
  38.     //multiply
  39.     XLong operator * (XLong const& r) const {
  40.         size_t m= 1 + 2*max(d.size(), r.d.size());
  41.         XLong ret{vector<Long>(m, 0ULL)};
  42.         for (size_t i=0; i<d.size(); i++) {
  43.             for (size_t j=0; j<r.d.size(); j++) {
  44.                 int p=i+j;
  45.                 Long dp=d[i]*r.d[j];
  46.                 ret.d[p] += dp%F;
  47.                 ret.d[p+1] += dp/F;
  48.             }
  49.         }
  50.         ret.inRange();
  51.         return ret;
  52.     }
  53.     //output
  54.     void print() {
  55.         inRange();
  56.         for (int i=d.size()-1; i>=0; i--) {
  57.             if (i==d.size()-1)
  58.                 printf("%lld", d[i]);
  59.             else
  60.                 printf("%08lld", d[i]);
  61.         }
  62.     }
  63. };
  64.  
  65. int main() {
  66. 	XLong A{1ULL};
  67. 	XLong B{1ULL};
  68. 	for (int i=2; i<12; i++) {
  69. 		XLong C=B*B + A;
  70. 		A=B;
  71. 		B=C;
  72. 		cout<<i<<' ';
  73. 		C.print();
  74. 		cout<<endl;
  75. 	}
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 2
3 5
4 27
5 734
6 538783
7 290287121823
8 84266613096281243382112
9 7100862082718357559748563880517486086728702367
10 50422242317787290639189291009890702507917377925161079229314384058371278254659634544914784801
11 2542402520353659447255836322014832373480442725597137048401938458888136467968523098505000150062722948351009708561995178835544955851791068846430550001251771967995534035485848806869311968
https://ideone.com/cieTAs
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!