fork download
copy 
  1. // 피보나치 수 4
  2. // https://w...content-available-to-author-only...c.net/problem/10826
  3. #include<iostream>
  4. #include<vector>
  5. #include<string>
  6. using namespace std;
  7.  
  8. class num {
  9. private:
  10.   vector<long long> n;
  11.   const static int MAX = (int)1e9;
  12.   const static int MAXLEN = 9;
  13. public:
  14.   num() {}
  15.   num(long long _n) { if(!_n) n.push_back(0); while(_n) { n.push_back(_n%MAX); _n/=MAX; }
  16.   }
  17.   ~num() { n.clear(); }
  18.   const num operator+ (const num& op) const {
  19.     num res;
  20.     int size = n.size(), sizeOP = op.n.size();
  21.     int N = size > sizeOP ? size : sizeOP;
  22.     int carry = 0;
  23.     for(int i=0; i<N; i++) {
  24.       int a = (i<size?n[i]:0) + (i<sizeOP?op.n[i]:0) + carry;
  25.       if(a >= MAX) { carry = 1; a -= MAX; }
  26.       else carry = 0;
  27.       res.n.push_back(a);
  28.     }
  29.     if(carry) res.n.push_back(carry);
  30.     return res;
  31.   }
  32.   const num operator* (const num& op) const {
  33.     num res;
  34.     int size = n.size(), sizeOP = op.n.size();
  35.     const num& b = (size < sizeOP ? op : *this);
  36.     const num& s = (size < sizeOP ? *this : op);
  37.     int bSize = size < sizeOP ? sizeOP : size;
  38.     int sSize = size < sizeOP ? size : sizeOP;
  39.     int resSize = bSize + sSize;
  40.     if(b.n[bSize-1]*s.n[sSize-1] < MAX) resSize--;
  41.     res.n.assign(resSize, 0);
  42.     int carry = 0;
  43.     for(int i=0; i<bSize; i++)
  44.       for(int j=0; j<sSize; j++) {
  45.         long long a = b.n[i] * s.n[j];
  46.         if(a >= MAX) { res.n[i+j+1] += a/MAX; a %= MAX; }
  47.         res.n[i+j] += a;
  48.         if(res.n[i+j]>=MAX) {
  49.           res.n[i+j+1] += res.n[i+j]/MAX;
  50.           res.n[i+j] %= MAX;
  51.         }
  52.       }
  53.     return res;
  54.   }
  55.   void prt() const {
  56.     int size = n.size();
  57.     cout << n[size-1];
  58.     for(int i=size-2; i>=0; i--) {
  59.       string s = to_string(n[i]);
  60.       int z = MAXLEN - s.size();
  61.       while(z--) cout << '0';
  62.       cout << s;
  63.     }
  64.   }
  65. };
  66.  
  67. typedef vector<vector<num>> Matrix;
  68.  
  69. Matrix operator * (const Matrix& a, const Matrix& b) {
  70.   int size = a.size();
  71.   Matrix res(size, vector<num>(size,0));
  72.   for(int i=0; i<size; i++)
  73.     for(int j=0; j<size; j++)
  74.       for(int k=0; k<size; k++)
  75.         res[i][j] = res[i][j] + a[i][k] * b[k][j];
  76.   return res;
  77. }
  78.  
  79. int main() {
  80.   ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  81.   int n; cin >> n;
  82.   if(n<=1) { cout << n; return 0; }
  83.   Matrix ans = {{1,0},{0,1}};
  84.   Matrix I = {{1,1},{1,0}};
  85.   while(n) {
  86.     if(n&1) ans = ans * I;
  87.     I = I * I;
  88.     n/=2;
  89.   }
  90.   ans[0][1].prt();
  91.   // num a(1), ans(0), t;
  92.   // while(n--) {
  93.   //   t = ans + a;
  94.   //   ans = a;
  95.   //   a = t;
  96.   // }
  97.   // ans.prt();
  98.   return 0;
  99. }
  100.  
Runtime error #stdin #stdout #stderr 0s 15248KB
comments (?)
stdin
copy 
5000
stdout
copy 
Standard output is empty
stderr
copy 
*** Error in `./prog': munmap_chunk(): invalid pointer: 0x00005646908a3270 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x70bcb)[0x2b364acacbcb]
/lib/x86_64-linux-gnu/libc.so.6(+0x76f96)[0x2b364acb2f96]
./prog(+0x120a)[0x56468fd1d20a]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf1)[0x2b364ac5c2b1]
./prog(+0x14aa)[0x56468fd1d4aa]
======= Memory map: ========
2b3649f5c000-2b3649f7f000 r-xp 00000000 fd:00 2710543                    /lib/x86_64-linux-gnu/ld-2.24.so
2b3649f7f000-2b3649f83000 rw-p 00000000 00:00 0 
2b3649f8c000-2b3649f91000 rw-p 00000000 00:00 0 
2b364a17f000-2b364a180000 r--p 00023000 fd:00 2710543                    /lib/x86_64-linux-gnu/ld-2.24.so
2b364a180000-2b364a181000 rw-p 00024000 fd:00 2710543                    /lib/x86_64-linux-gnu/ld-2.24.so
2b364a181000-2b364a182000 rw-p 00000000 00:00 0 
2b364a182000-2b364a2f4000 r-xp 00000000 fd:00 2712611                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2b364a2f4000-2b364a4f4000 ---p 00172000 fd:00 2712611                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2b364a4f4000-2b364a4fe000 r--p 00172000 fd:00 2712611                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2b364a4fe000-2b364a500000 rw-p 0017c000 fd:00 2712611                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2b364a500000-2b364a504000 rw-p 00000000 00:00 0 
2b364a504000-2b364a607000 r-xp 00000000 fd:00 2710572                    /lib/x86_64-linux-gnu/libm-2.24.so
2b364a607000-2b364a806000 ---p 00103000 fd:00 2710572                    /lib/x86_64-linux-gnu/libm-2.24.so
2b364a806000-2b364a807000 r--p 00102000 fd:00 2710572                    /lib/x86_64-linux-gnu/libm-2.24.so
2b364a807000-2b364a808000 rw-p 00103000 fd:00 2710572                    /lib/x86_64-linux-gnu/libm-2.24.so
2b364a808000-2b364a81e000 r-xp 00000000 fd:00 2710510                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2b364a81e000-2b364aa1d000 ---p 00016000 fd:00 2710510                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2b364aa1d000-2b364aa1e000 r--p 00015000 fd:00 2710510                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2b364aa1e000-2b364aa1f000 rw-p 00016000 fd:00 2710510                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2b364aa1f000-2b364aa37000 r-xp 00000000 fd:00 2710529                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2b364aa37000-2b364ac36000 ---p 00018000 fd:00 2710529                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2b364ac36000-2b364ac37000 r--p 00017000 fd:00 2710529                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2b364ac37000-2b364ac38000 rw-p 00018000 fd:00 2710529                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2b364ac38000-2b364ac3c000 rw-p 00000000 00:00 0 
2b364ac3c000-2b364add1000 r-xp 00000000 fd:00 2710666                    /lib/x86_64-linux-gnu/libc-2.24.so
2b364add1000-2b364afd0000 ---p 00195000 fd:00 2710666                    /lib/x86_64-linux-gnu/libc-2.24.so
2b364afd0000-2b364afd4000 r--p 00194000 fd:00 2710666                    /lib/x86_64-linux-gnu/libc-2.24.so
2b364afd4000-2b364afd6000 rw-p 00198000 fd:00 2710666                    /lib/x86_64-linux-gnu/libc-2.24.so
2b364afd6000-2b364afda000 rw-p 00000000 00:00 0 
56468fd1c000-56468fd20000 r-xp 00000000 fd:00 14969794                   /home/LLOX5u/prog
56468ff1f000-56468ff20000 r--p 00003000 fd:00 14969794                   /home/LLOX5u/prog
56468ff20000-56468ff21000 rw-p 00004000 fd:00 14969794                   /home/LLOX5u/prog
564690873000-5646908a5000 rw-p 00000000 00:00 0                          [heap]
7ffeed743000-7ffeed764000 rw-p 00000000 00:00 0                          [stack]
7ffeed7a0000-7ffeed7a2000 r-xp 00000000 00:00 0                          [vdso]
7ffeed7a2000-7ffeed7a4000 r--p 00000000 00:00 0                          [vvar]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
https://ideone.com/CHLWBX
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!