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

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!