fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<string>
  4. using namespace std;
  5.  
  6. class num {
  7. private:
  8.   vector<long long> n;
  9.   const static int MAX = (int)1e9;
  10.   const static int MAXLEN = 9;
  11. public:
  12.   num() {}
  13.   num(long long _n) { if(!_n) n.push_back(0); while(_n) { n.push_back(_n%MAX); _n/=MAX; }
  14.   }
  15.   ~num() { n.clear(); }
  16.   const num operator+ (const num& op) const {
  17.     num res;
  18.     int size = n.size(), sizeOP = op.n.size();
  19.     int N = size > sizeOP ? size : sizeOP;
  20.     int carry = 0;
  21.     for(int i=0; i<N; i++) {
  22.       int a = (i<size?n[i]:0) + (i<sizeOP?op.n[i]:0) + carry;
  23.       if(a >= MAX) { carry = 1; a -= MAX; }
  24.       else carry = 0;
  25.       res.n.push_back(a);
  26.     }
  27.     if(carry) res.n.push_back(carry);
  28.     return res;
  29.   }
  30.   const num operator* (const num& op) const {
  31.     num res;
  32.     int size = n.size(), sizeOP = op.n.size();
  33.     const num& b = (size < sizeOP ? op : *this);
  34.     const num& s = (size < sizeOP ? *this : op);
  35.     int bSize = size < sizeOP ? sizeOP : size;
  36.     int sSize = size < sizeOP ? size : sizeOP;
  37.     int resSize = bSize + sSize;
  38.     if(b.n[bSize-1]*s.n[sSize-1] < MAX) resSize--;
  39.     res.n.assign(resSize, 0);
  40.     int carry = 0;
  41.     for(int i=0; i<bSize; i++)
  42.       for(int j=0; j<sSize; j++) {
  43.         long long a = b.n[i] * s.n[j];
  44.         if(a >= MAX) { res.n[i+j+1] += a/MAX; a %= MAX; }
  45.         res.n[i+j] += a;
  46.         if(res.n[i+j]>=MAX) {
  47.           res.n[i+j+1] += res.n[i+j]/MAX;
  48.           res.n[i+j] %= MAX;
  49.         }
  50.       }
  51.     return res;
  52.   }
  53.   void prt() const {
  54.     int size = n.size();
  55.     cout << n[size-1];
  56.     for(int i=size-2; i>=0; i--) {
  57.       string s = to_string(n[i]);
  58.       int z = MAXLEN - s.size();
  59.       while(z--) cout << '0';
  60.       cout << s;
  61.     }
  62.   }
  63. };
  64.  
  65. typedef vector<vector<num>> Matrix;
  66.  
  67. Matrix operator * (const Matrix& a, const Matrix& b) {
  68.   int size = a.size();
  69.   Matrix res(size, vector<num>(size,0));
  70.   for(int i=0; i<size; i++)
  71.     for(int j=0; j<size; j++)
  72.       for(int k=0; k<size; k++)
  73.         res[i][j] = res[i][j] + a[i][k] * b[k][j];
  74.   return res;
  75. }
  76.  
  77. int main() {
  78.   ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  79.   int n; cin >> n;
  80.   if(n<=1) { cout << n; return 0; }
  81.   Matrix ans = {{1,0},{0,1}};
  82.   Matrix I = {{1,1},{1,0}};
  83.   while(n) {
  84.     if(n&1) ans = ans * I;
  85.     I = I * I;
  86.     n/=2;
  87.   }
  88.   ans[0][1].prt();
  89.   // num a(1), ans(0), t;
  90.   // while(n--) {
  91.   //   t = ans + a;
  92.   //   ans = a;
  93.   //   a = t;
  94.   // }
  95.   // ans.prt();
  96.   return 0;
  97. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
0
stdout
copy 
Standard output is empty
https://ideone.com/xuppp6
language:
C++14 (gcc 8.3)
created:
5 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!