fork(5) download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. const int base = 1000000000;
  7. const int base_digits = 9;
  8.  
  9. struct bigint {
  10.     vector<int> a;
  11.     int sign;
  12.  
  13.     bigint() :
  14.         sign(1) {
  15.     }
  16.  
  17.     bigint(long long v) {
  18.         *this = v;
  19.     }
  20.  
  21.     bigint(const string &s) {
  22.         read(s);
  23.     }
  24.  
  25.     void operator=(const bigint &v) {
  26.         sign = v.sign;
  27.         a = v.a;
  28.     }
  29.  
  30.     void operator=(long long v) {
  31.         sign = 1;
  32.         if (v < 0)
  33.             sign = -1, v = -v;
  34.         for (; v > 0; v = v / base)
  35.             a.push_back(v % base);
  36.     }
  37.  
  38.     bigint operator+(const bigint &v) const {
  39.         if (sign == v.sign) {
  40.             bigint res = v;
  41.  
  42.             for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
  43.                 if (i == (int) res.a.size())
  44.                     res.a.push_back(0);
  45.                 res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
  46.                 carry = res.a[i] >= base;
  47.                 if (carry)
  48.                     res.a[i] -= base;
  49.             }
  50.             return res;
  51.         }
  52.         return *this - (-v);
  53.     }
  54.  
  55.     bigint operator-(const bigint &v) const {
  56.         if (sign == v.sign) {
  57.             if (abs() >= v.abs()) {
  58.                 bigint res = *this;
  59.                 for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
  60.                     res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
  61.                     carry = res.a[i] < 0;
  62.                     if (carry)
  63.                         res.a[i] += base;
  64.                 }
  65.                 res.trim();
  66.                 return res;
  67.             }
  68.             return -(v - *this);
  69.         }
  70.         return *this + (-v);
  71.     }
  72.  
  73.     void operator*=(int v) {
  74.         if (v < 0)
  75.             sign = -sign, v = -v;
  76.         for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
  77.             if (i == (int) a.size())
  78.                 a.push_back(0);
  79.             long long cur = a[i] * (long long) v + carry;
  80.             carry = (int) (cur / base);
  81.             a[i] = (int) (cur % base);
  82.             //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  83.         }
  84.         trim();
  85.     }
  86.  
  87.     bigint operator*(int v) const {
  88.         bigint res = *this;
  89.         res *= v;
  90.         return res;
  91.     }
  92.  
  93.     friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
  94.         int norm = base / (b1.a.back() + 1);
  95.         bigint a = a1.abs() * norm;
  96.         bigint b = b1.abs() * norm;
  97.         bigint q, r;
  98.         q.a.resize(a.a.size());
  99.  
  100.         for (int i = a.a.size() - 1; i >= 0; i--) {
  101.             r *= base;
  102.             r += a.a[i];
  103.             int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  104.             int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  105.             int d = ((long long) base * s1 + s2) / b.a.back();
  106.             r -= b * d;
  107.             while (r < 0)
  108.                 r += b, --d;
  109.             q.a[i] = d;
  110.         }
  111.  
  112.         q.sign = a1.sign * b1.sign;
  113.         r.sign = a1.sign;
  114.         q.trim();
  115.         r.trim();
  116.         return make_pair(q, r / norm);
  117.     }
  118.  
  119.     bigint operator/(const bigint &v) const {
  120.         return divmod(*this, v).first;
  121.     }
  122.  
  123.     bigint operator%(const bigint &v) const {
  124.         return divmod(*this, v).second;
  125.     }
  126.  
  127.     void operator/=(int v) {
  128.         if (v < 0)
  129.             sign = -sign, v = -v;
  130.         for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  131.             long long cur = a[i] + rem * (long long) base;
  132.             a[i] = (int) (cur / v);
  133.             rem = (int) (cur % v);
  134.         }
  135.         trim();
  136.     }
  137.  
  138.     bigint operator/(int v) const {
  139.         bigint res = *this;
  140.         res /= v;
  141.         return res;
  142.     }
  143.  
  144.     int operator%(int v) const {
  145.         if (v < 0)
  146.             v = -v;
  147.         int m = 0;
  148.         for (int i = a.size() - 1; i >= 0; --i)
  149.             m = (a[i] + m * (long long) base) % v;
  150.         return m * sign;
  151.     }
  152.  
  153.     void operator+=(const bigint &v) {
  154.         *this = *this + v;
  155.     }
  156.     void operator-=(const bigint &v) {
  157.         *this = *this - v;
  158.     }
  159.     void operator*=(const bigint &v) {
  160.         *this = *this * v;
  161.     }
  162.     void operator/=(const bigint &v) {
  163.         *this = *this / v;
  164.     }
  165.  
  166.     bool operator<(const bigint &v) const {
  167.         if (sign != v.sign)
  168.             return sign < v.sign;
  169.         if (a.size() != v.a.size())
  170.             return a.size() * sign < v.a.size() * v.sign;
  171.         for (int i = a.size() - 1; i >= 0; i--)
  172.             if (a[i] != v.a[i])
  173.                 return a[i] * sign < v.a[i] * sign;
  174.         return false;
  175.     }
  176.  
  177.     bool operator>(const bigint &v) const {
  178.         return v < *this;
  179.     }
  180.     bool operator<=(const bigint &v) const {
  181.         return !(v < *this);
  182.     }
  183.     bool operator>=(const bigint &v) const {
  184.         return !(*this < v);
  185.     }
  186.     bool operator==(const bigint &v) const {
  187.         return !(*this < v) && !(v < *this);
  188.     }
  189.     bool operator!=(const bigint &v) const {
  190.         return *this < v || v < *this;
  191.     }
  192.  
  193.     void trim() {
  194.         while (!a.empty() && !a.back())
  195.             a.pop_back();
  196.         if (a.empty())
  197.             sign = 1;
  198.     }
  199.  
  200.     bool isZero() const {
  201.         return a.empty() || (a.size() == 1 && !a[0]);
  202.     }
  203.  
  204.     bigint operator-() const {
  205.         bigint res = *this;
  206.         res.sign = -sign;
  207.         return res;
  208.     }
  209.  
  210.     bigint abs() const {
  211.         bigint res = *this;
  212.         res.sign *= res.sign;
  213.         return res;
  214.     }
  215.  
  216.     long long longValue() const {
  217.         long long res = 0;
  218.         for (int i = a.size() - 1; i >= 0; i--)
  219.             res = res * base + a[i];
  220.         return res * sign;
  221.     }
  222.  
  223.     friend bigint gcd(const bigint &a, const bigint &b) {
  224.         return b.isZero() ? a : gcd(b, a % b);
  225.     }
  226.     friend bigint lcm(const bigint &a, const bigint &b) {
  227.         return a / gcd(a, b) * b;
  228.     }
  229.  
  230.     void read(const string &s) {
  231.         sign = 1;
  232.         a.clear();
  233.         int pos = 0;
  234.         while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  235.             if (s[pos] == '-')
  236.                 sign = -sign;
  237.             ++pos;
  238.         }
  239.         for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  240.             int x = 0;
  241.             for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  242.                 x = x * 10 + s[j] - '0';
  243.             a.push_back(x);
  244.         }
  245.         trim();
  246.     }
  247.  
  248.     friend istream& operator>>(istream &stream, bigint &v) {
  249.         string s;
  250.         stream >> s;
  251.         v.read(s);
  252.         return stream;
  253.     }
  254.  
  255.     friend ostream& operator<<(ostream &stream, const bigint &v) {
  256.         if (v.sign == -1)
  257.             stream << '-';
  258.         stream << (v.a.empty() ? 0 : v.a.back());
  259.         for (int i = (int) v.a.size() - 2; i >= 0; --i)
  260.             stream << setw(base_digits) << setfill('0') << v.a[i];
  261.         return stream;
  262.     }
  263.  
  264.     static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
  265.         vector<long long> p(max(old_digits, new_digits) + 1);
  266.         p[0] = 1;
  267.         for (int i = 1; i < (int) p.size(); i++)
  268.             p[i] = p[i - 1] * 10;
  269.         vector<int> res;
  270.         long long cur = 0;
  271.         int cur_digits = 0;
  272.         for (int i = 0; i < (int) a.size(); i++) {
  273.             cur += a[i] * p[cur_digits];
  274.             cur_digits += old_digits;
  275.             while (cur_digits >= new_digits) {
  276.                 res.push_back(int(cur % p[new_digits]));
  277.                 cur /= p[new_digits];
  278.                 cur_digits -= new_digits;
  279.             }
  280.         }
  281.         res.push_back((int) cur);
  282.         while (!res.empty() && !res.back())
  283.             res.pop_back();
  284.         return res;
  285.     }
  286.  
  287.     typedef vector<long long> vll;
  288.  
  289.     static vll karatsubaMultiply(const vll &a, const vll &b) {
  290.         int n = a.size();
  291.         vll res(n + n);
  292.         if (n <= 32) {
  293.             for (int i = 0; i < n; i++)
  294.                 for (int j = 0; j < n; j++)
  295.                     res[i + j] += a[i] * b[j];
  296.             return res;
  297.         }
  298.  
  299.         int k = n >> 1;
  300.         vll a1(a.begin(), a.begin() + k);
  301.         vll a2(a.begin() + k, a.end());
  302.         vll b1(b.begin(), b.begin() + k);
  303.         vll b2(b.begin() + k, b.end());
  304.  
  305.         vll a1b1 = karatsubaMultiply(a1, b1);
  306.         vll a2b2 = karatsubaMultiply(a2, b2);
  307.  
  308.         for (int i = 0; i < k; i++)
  309.             a2[i] += a1[i];
  310.         for (int i = 0; i < k; i++)
  311.             b2[i] += b1[i];
  312.  
  313.         vll r = karatsubaMultiply(a2, b2);
  314.         for (int i = 0; i < (int) a1b1.size(); i++)
  315.             r[i] -= a1b1[i];
  316.         for (int i = 0; i < (int) a2b2.size(); i++)
  317.             r[i] -= a2b2[i];
  318.  
  319.         for (int i = 0; i < (int) r.size(); i++)
  320.             res[i + k] += r[i];
  321.         for (int i = 0; i < (int) a1b1.size(); i++)
  322.             res[i] += a1b1[i];
  323.         for (int i = 0; i < (int) a2b2.size(); i++)
  324.             res[i + n] += a2b2[i];
  325.         return res;
  326.     }
  327.  
  328.     bigint operator*(const bigint &v) const {
  329.         vector<int> a6 = convert_base(this->a, base_digits, 6);
  330.         vector<int> b6 = convert_base(v.a, base_digits, 6);
  331.         vll a(a6.begin(), a6.end());
  332.         vll b(b6.begin(), b6.end());
  333.         while (a.size() < b.size())
  334.             a.push_back(0);
  335.         while (b.size() < a.size())
  336.             b.push_back(0);
  337.         while (a.size() & (a.size() - 1))
  338.             a.push_back(0), b.push_back(0);
  339.         vll c = karatsubaMultiply(a, b);
  340.         bigint res;
  341.         res.sign = sign * v.sign;
  342.         for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  343.             long long cur = c[i] + carry;
  344.             res.a.push_back((int) (cur % 1000000));
  345.             carry = (int) (cur / 1000000);
  346.         }
  347.         res.a = convert_base(res.a, 6, base_digits);
  348.         res.trim();
  349.         return res;
  350.     }
  351. };
  352.  
  353. int main()
  354. {
  355.     int n,i;
  356.     string x,y;
  357.  
  358.     cin>>x>>y;
  359.     cin>>n;
  360.      bigint a(x),b(y);
  361.     bigint big[n+1];
  362.     big[0]=a;
  363.     big[1]=b;
  364.    // big[2]=big[1]*big[1];
  365.     //cout<<big[2];
  366.     for(i=2;i<n;i++)
  367.         {
  368.         big[i]=big[i-1]*big[i-1];
  369.         big[i]=big[i]+big[i-2];
  370.         //cout<<big[i]<<endl;
  371.     }
  372.  
  373.    cout<<big[n-1];
  374. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
0 1 5
stdout
copy 
5
https://ideone.com/PLVzvu
language:
C++ (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!