fork download 
  1. #include <vector>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <iterator>
  5. #include <string>
  6. #include <algorithm>
  7. #include <exception>
  8. #include <stdexcept>
  9. #include <cstring>
  10. #include <cstdio>
  11. #include <cstdlib>
  12.  
  13. class BigInteger
  14. {
  15. public: 
  16.     BigInteger()
  17.     {
  18.         _data.push_back(0);
  19.     }
  20.  
  21.     BigInteger(long long x)
  22.     {
  23.         while(x)
  24.         {
  25.             _data.push_back(x % _base);
  26.             x /= _base;
  27.         }
  28.  
  29.         if(_data.empty()) _data.push_back(0);
  30.     }
  31.  
  32.     BigInteger(unsigned long long x)
  33.     {
  34.         while(x)
  35.         {
  36.             _data.push_back(x % _base);
  37.             x /= _base;
  38.         }
  39.  
  40.         if(_data.empty()) _data.push_back(0);
  41.     }
  42.  
  43.     BigInteger(int x) : BigInteger((long long)x) {}
  44.     BigInteger(unsigned int x) : BigInteger((unsigned long long)x) {}
  45.     BigInteger(short x) : BigInteger((long long)x) {}
  46.     BigInteger(unsigned short x) : BigInteger((unsigned long long)x) {}
  47.     BigInteger(char x) : BigInteger((long long)x) {}
  48.     BigInteger(unsigned char x) : BigInteger((unsigned long long)x) {}
  49.  
  50.     BigInteger(std::string &s)
  51.     {
  52.         for(int i = (int)s.size(); i > 0; i -= 9)
  53.             if(i < 9)
  54.                 _data.push_back(atoi(s.substr(0, i).data()));
  55.             else
  56.                 _data.push_back(atoi(s.substr(i - 9, 9).data()));
  57.  
  58.         while(_data.size() > 1 && _data.back() == 0)
  59.             _data.pop_back();
  60.     }
  61.  
  62.     BigInteger(const char *s)  
  63.     {
  64.         std::string d = s;
  65.  
  66.         for(int i = (int)d.size(); i > 0; i -= 9)
  67.             if(i < 9)
  68.                 _data.push_back(atoi(d.substr(0, i).data()));
  69.             else
  70.                 _data.push_back(atoi(d.substr(i - 9, 9).data()));
  71.  
  72.         while(_data.size() > 1 && _data.back() == 0)
  73.             _data.pop_back();
  74.     }
  75.  
  76.     BigInteger(const BigInteger& b)
  77.     {
  78.         _data.resize(b._data.size());
  79.         std::copy(b._data.begin(), b._data.end(), _data.begin());
  80.     }
  81.  
  82.     void ToString(char *s) const
  83.     {
  84.         sprintf(s, "%d", _data.empty() ? 0 : _data.back());
  85.         for(int i = (int)_data.size() - 2; i >= 0; i--)
  86.             sprintf(s, "%s%09d", s, _data[i]);
  87.     }
  88.  
  89.     std::string ToString() const
  90.     {
  91.         char *buff = (char*)malloc(20);
  92.  
  93.         sprintf(buff, "%d", _data.empty() ? 0 : _data.back());
  94.         std::string res = buff;
  95.  
  96.         for(int i = (int)_data.size() - 2; i >= 0; i--)
  97.         {
  98.             sprintf(buff, "%09d", _data[i]);
  99.             res += buff;
  100.         }
  101.  
  102.         free(buff);
  103.  
  104.         return res;
  105.     }
  106.  
  107.     friend const BigInteger operator+(BigInteger &i);
  108.     friend const BigInteger& operator++(BigInteger &i);
  109.     friend const BigInteger& operator--(BigInteger &i);
  110.     friend const BigInteger operator++(BigInteger &i, int);
  111.     friend const BigInteger operator--(BigInteger &i, int);
  112.  
  113.     friend const BigInteger operator+(const BigInteger &c, const BigInteger &b);
  114.     friend const BigInteger operator-(const BigInteger &c, const BigInteger &b);
  115.     friend const BigInteger operator*(const BigInteger &a, const BigInteger &b);
  116.     friend const BigInteger operator/(const BigInteger &a, const BigInteger &b);
  117.     friend const BigInteger operator%(const BigInteger &a, const BigInteger &b);
  118.  
  119.     friend BigInteger& operator+=(BigInteger &a, const BigInteger &b);
  120.     friend BigInteger& operator-=(BigInteger &a, const BigInteger &b);
  121.     friend BigInteger& operator*=(BigInteger &a, const BigInteger &b);
  122.     friend BigInteger& operator/=(BigInteger &a, const BigInteger &b);
  123.     friend BigInteger& operator%=(BigInteger &a, const BigInteger &b);
  124.  
  125.     friend bool operator==(const BigInteger &a, const BigInteger &b);
  126.     friend bool operator<=(const BigInteger &a, const BigInteger &b);
  127.     friend bool operator>=(const BigInteger &a, const BigInteger &b);
  128.     friend bool operator<(const BigInteger &a, const BigInteger &b);
  129.     friend bool operator>(const BigInteger &a, const BigInteger &b);
  130.     friend bool operator!=(const BigInteger &a, const BigInteger &b);
  131.  
  132.     /*operator long long() const
  133.     {
  134.         long long res = 0, b = 1;
  135.         for(size_t i = 0; i < _data.size(); i++)
  136.         {
  137.             res += b * _data[i];
  138.             b *= BigInteger::_base;
  139.         }
  140.         return res;
  141.     }
  142.     
  143.     operator unsigned long long()
  144.     {
  145.         unsigned long long res = 0, b = 1;
  146.         for(size_t i = 0; i < _data.size(); i++)
  147.         {
  148.             res += b * _data[i];
  149.             b *= BigInteger::_base;
  150.         }
  151.         return res;
  152.     }*/
  153.  
  154.     friend std::istream& operator>>(std::istream &is, BigInteger &i)
  155.     {
  156.         std::string s;
  157.         is >> s;
  158.         i = BigInteger(s);
  159.         return is;
  160.     }
  161.  
  162.     friend std::ostream& operator<<(std::ostream &os, const BigInteger &i)
  163.     {
  164.         os << i.ToString();
  165.         return os;
  166.     }
  167.  
  168. private:
  169.     static const int _base = 1000 * 1000 * 1000;
  170.     std::vector<int> _data;
  171.  
  172.     int _cmp(const BigInteger &a, const BigInteger &b) const //a - b, 1 if a > b
  173.     {
  174.         if(a._data.size() > b._data.size()) return 1;
  175.         if(a._data.size() < b._data.size()) return -1;
  176.  
  177.         for(int i = (int)a._data.size() - 1; i >= 0; i--)
  178.         {
  179.             if(a._data[i] > b._data[i]) return 1;
  180.             if(a._data[i] < b._data[i]) return -1;
  181.         }
  182.  
  183.         return 0;
  184.     }
  185.  
  186.     BigInteger _div_short(const BigInteger &c, int b, int &mod) const
  187.     {
  188.         mod = 0;
  189.         BigInteger a = c;
  190.         for(int i = (int)a._data.size() - 1; i >= 0; i--) 
  191.         {
  192.             long long cur = a._data[i] + mod * 1ll * BigInteger::_base;
  193.             a._data[i] = int(cur / b);
  194.             mod = int(cur % b);
  195.         }
  196.  
  197.         while (a._data.size() > 1 && a._data.back() == 0)
  198.             a._data.pop_back();
  199.  
  200.         return a;
  201.     }
  202.  
  203.     bool _is_zero() const
  204.     {
  205.         return _data.size() == 1 && _data[0] == 0;
  206.     }
  207. };
  208.  
  209. const BigInteger operator+(const BigInteger &i) 
  210. {
  211.     return BigInteger(i);
  212. }
  213.  
  214. const BigInteger& operator++(BigInteger &i) 
  215. {
  216.     int j = 0;
  217.     i._data[0]++;
  218.  
  219.     while(i._data[j] >= BigInteger::_base)
  220.     {
  221.         if(j == (int)i._data.size() - 1) i._data.push_back(1); else i._data[j + 1]++;
  222.         i._data[j] -= BigInteger::_base;
  223.         j++;
  224.     }
  225.  
  226.     return i;
  227. }
  228.  
  229. const BigInteger operator++(BigInteger &i, int) 
  230. {
  231.     BigInteger old = BigInteger(i);
  232.  
  233.     int j = 0;
  234.     i._data[0]++;
  235.  
  236.     while(i._data[j] >= BigInteger::_base)
  237.     {
  238.         if(j == (int)i._data.size() - 1) i._data.push_back(1); else i._data[j + 1]++;
  239.         i._data[j] -= BigInteger::_base;
  240.         j++;
  241.     }
  242.  
  243.     return old;
  244. }
  245.  
  246. //TODO: Optimize
  247. const BigInteger& operator--(BigInteger &i) 
  248. {
  249.     if(!i._is_zero()) i = i - 1;
  250.     return i;
  251. }
  252.  
  253. //TODO: Optimize
  254. const BigInteger operator--(BigInteger &i, int) 
  255. {
  256.     BigInteger old = BigInteger(i);
  257.     if(!i._is_zero()) i = i - 1;
  258.     return old;
  259. }
  260.  
  261. const BigInteger operator+(const BigInteger &c, const BigInteger &b)
  262. {
  263.     BigInteger a = c;
  264.  
  265.     int carry = 0;
  266.     for(size_t i = 0; i < std::max(a._data.size(), b._data.size()) || carry; i++) 
  267.     {
  268.         if(i == a._data.size()) a._data.push_back(0);
  269.         a._data[i] += carry + (i < b._data.size() ? b._data[i] : 0);
  270.         carry = a._data[i] >= BigInteger::_base;
  271.         if(carry) a._data[i] -= BigInteger::_base;
  272.     }   
  273.  
  274.     return a;       
  275. }
  276.  
  277. const BigInteger operator-(const BigInteger &c, const BigInteger &b)
  278. {
  279.     if(c < b) throw std::invalid_argument("a - b, a must b greater or equal zero");
  280.     BigInteger a = c;
  281.  
  282.     int carry = 0;
  283.     for(size_t i = 0; i < b._data.size() || carry; i++) 
  284.     {
  285.         a._data[i] -= carry + (i < b._data.size() ? b._data[i] : 0);
  286.         carry = a._data[i] < 0;
  287.         if(carry) a._data[i] += BigInteger::_base;
  288.     }
  289.  
  290.     while(a._data.size() > 1 && a._data.back() == 0)
  291.         a._data.pop_back();
  292.  
  293.     return a;       
  294. }
  295.  
  296. const BigInteger operator*(const BigInteger &a, const BigInteger &b)
  297. {
  298.     BigInteger c;
  299.     c._data.resize(a._data.size() + b._data.size());
  300.  
  301.     for(size_t i = 0; i < a._data.size(); i++)
  302.         for(int j = 0, carry = 0; j < (int)b._data.size() || carry; j++) 
  303.         {
  304.             long long cur = c._data[i + j] + a._data[i] * 1ll * (j < (int)b._data.size() ? b._data[j] : 0) + carry;
  305.             c._data[i + j] = int(cur % BigInteger::_base);
  306.             carry = int(cur / BigInteger::_base);
  307.         }
  308.  
  309.     while(c._data.size() > 1 && c._data.back() == 0)
  310.         c._data.pop_back();
  311.  
  312.     return c;       
  313. }
  314.  
  315. //TODO: Division by zero
  316. const BigInteger operator/(const BigInteger &a, const BigInteger &b)
  317. {
  318.     if(b._is_zero()) throw std::invalid_argument("division by zero");
  319.     BigInteger l = 0, r = a + 1, m;
  320.     int t;
  321.     while(r - l > 1)
  322.     {
  323.         //m = (r + l) / 2;
  324.         m = a._div_short(r + l, 2, t);
  325.         if(b * m <= a) l = m; else r = m;
  326.     }
  327.     return l;
  328. }
  329.  
  330. //TODO: Division by zero
  331. const BigInteger operator%(const BigInteger &a, const BigInteger &b)
  332. {
  333.     if(b._is_zero()) throw std::invalid_argument("division by zero");
  334.     BigInteger l = 0, r = a + 1, m;
  335.     int t;
  336.     while(r - l > 1)
  337.     {
  338.         //m = (r + l) / 2;
  339.         m = a._div_short(r + l, 2, t);
  340.         if(b * m <= a) l = m; else r = m;
  341.     }
  342.     return a - b * l;
  343. }
  344.  
  345. BigInteger& operator+=(BigInteger &a, const BigInteger &b)
  346. {
  347.     int carry = 0;
  348.     for(size_t i = 0; i < std::max(a._data.size(), b._data.size()) || carry; i++) 
  349.     {
  350.         if(i == a._data.size()) a._data.push_back(0);
  351.         a._data[i] += carry + (i < b._data.size() ? b._data[i] : 0);
  352.         carry = a._data[i] >= BigInteger::_base;
  353.         if(carry) a._data[i] -= BigInteger::_base;
  354.     }   
  355.     return a;
  356. }
  357.  
  358. BigInteger& operator-=(BigInteger &a, const BigInteger &b)
  359. {
  360.     int carry = 0;
  361.     for(size_t i = 0; i < b._data.size() || carry; i++) 
  362.     {
  363.         a._data[i] -= carry + (i < b._data.size() ? b._data[i] : 0);
  364.         carry = a._data[i] < 0;
  365.         if(carry) a._data[i] += BigInteger::_base;
  366.     }
  367.  
  368.     while(a._data.size() > 1 && a._data.back() == 0)
  369.         a._data.pop_back();
  370.  
  371.     return a;
  372. }
  373.  
  374. BigInteger& operator*=(BigInteger &a, const BigInteger &b)
  375. {
  376.     a = a * b;
  377.     return a;
  378. }
  379.  
  380. BigInteger& operator/=(BigInteger &a, const BigInteger &b)
  381. {
  382.     a = a / b;
  383.     return a;
  384. }
  385.  
  386. BigInteger& operator%=(BigInteger &a, const BigInteger &b)
  387. {
  388.     a = a % b;
  389.     return a;
  390. }
  391.  
  392. bool operator==(const BigInteger& a, const BigInteger& b)
  393. {
  394.     return a._cmp(a, b) == 0;
  395. }
  396.  
  397. bool operator<=(const BigInteger& a, const BigInteger& b)
  398. {
  399.     return a._cmp(a, b) <= 0;
  400. }
  401.  
  402. bool operator>=(const BigInteger& a, const BigInteger& b)
  403. {
  404.     return a._cmp(a, b) >= 0;
  405. }
  406.  
  407. bool operator<(const BigInteger& a, const BigInteger& b)
  408. {
  409.     return a._cmp(a, b) < 0;
  410. }
  411.  
  412. bool operator>(const BigInteger& a, const BigInteger& b)
  413. {
  414.     return a._cmp(a, b) > 0;
  415. }
  416.  
  417. bool operator!=(const BigInteger& a, const BigInteger& b)
  418. {
  419.     return a._cmp(a, b) != 0;
  420. }
  421.  
  422. int main()
  423. {
  424.     int n;
  425.     std::cin >> n;
  426.     std::vector<BigInteger> f = { BigInteger(0), BigInteger(1) };
  427.     for(int i = 2; i <= n; i++) f.push_back(f[i - 1] + f[i - 2]);
  428.     std::cout << f[n].ToString() << std::endl;
  429.     return 0;
  430. }
Success #stdin #stdout 0.02s 9560KB
comments (?)
stdin 
Standard input is empty
stdout 
6573029536785619260503920968745166524174800869732981663735443560807995648678797637500092292663397603715422461602134228160610100626433298744802567909231655540631292897759414981231630235426862481446644018654578848612070903309763254052924088364268263279351948633057560046681788403050669571066679652036225039559293922665194232228275243447623544249009003009333127068689549814323168286803566030318011831396711856417987793223283113287565127216545444769376124477376069361732059886102285639218079175911185416660811742461318084637828481715865777611987626045896079384998631729350663247642886784960852264742444236982879519611622891479796907814281451652000047723618872605097303700247815707640219192974472440548395844170611234360820131000053241042579185298315956758942968892711582165713648315145745812172868908259240551481396092265569783883838130063267283703311899406458942661752461999560482921019413323582498204416891216586686702183033069823001873352968615650552775407384281065257678279732948094478631056546619352074375600081760911174669914460211625246998108315337497721290422909016565708831215580295802155643816267850592134638364791185714843210717619716415897087610773177822353473596895518373323048863029341455966094401686780679690444927239367707621653936268381022247664365521702107408248398246562344228404011532683783393656976760107642719848957503636119616886777473119077032089020056649919544349926242214790170549774450825631210812031216471015510968770435096093136344582128365513636233441973604425446457266520349331486359832489853961944211773004017295329760290680633382731960566297083794914986946836767155407598939343610715822518003245552549403333486113297126878181984177258446784411106938065297540017776224788470681283053319743755451288137761528615051809992543751746108789747400824640566221028117768049024232371075424154153718892756613322690498064533371659532119140589217491980818864306342391126537710044588093327169035551179734074623809071636764630738364893894361739073181590868655017262901298985070723366531447973366837848359101370234625382511080000985364185815606644519816129286246926832593690358276001738549464105307133743367431169739607544794368798178498704745881253129075217917732646454358080053300910439929222486447600119776423756384733069739990519249108812112638017604228917149413613371263465667261595624572993215913934190405876770
https://ideone.com/rOVwXg
language:
C++ (gcc 8.3)
created:
7 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!