library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub beet-aizu/library

:heavy_check_mark: tools/bigint.cpp

Depends on

Verified with

Code

#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../convolution/fastfouriertransform.cpp"
#undef call_from_test

#endif
//BEGIN CUT HERE
struct bigint {
  using ll = long long;
  using vll = vector<ll>;

  inline static constexpr ll base_digits = 9;
  inline static constexpr ll base = 1000000000;

  vll a;
  ll sign;

  bigint():sign(1){}

  bigint(ll v){*this=v;}

  bigint(const string &s){read(s);}

  static bigint add_identity(){return bigint(0);}
  static bigint mul_identity(){return bigint(1);}

  void operator=(ll v){
    sign=1;
    if(v<0) sign=-1,v=-v;
    for(;v>0;v=v/base) a.emplace_back(v%base);
  }

  bigint operator+(const bigint &v) const{
    if(sign==v.sign){
      bigint res=v;
      for(ll i=0,carry=0;i<(ll)max(a.size(),v.a.size()) or carry;++i){
        if(i==(ll)res.a.size()) res.a.emplace_back(0);
        res.a[i]+=carry+(i<(ll)a.size()?a[i]:0);
        carry=res.a[i]>=base;
        if(carry) res.a[i]-=base;
      }
      return res;
    }
    return *this-(-v);
  }

  bigint operator-(const bigint &v) const{
    if(sign==v.sign){
      if(abs()>=v.abs()){
        bigint res=*this;
        for(ll i=0,carry=0;i<(ll)v.a.size() or carry;++i){
          res.a[i]-=carry+(i<(ll)v.a.size()?v.a[i]:0);
          carry=res.a[i]<0;
          if(carry) res.a[i]+=base;
        }
        res.trim();
        return res;
      }
      return -(v-*this);
    }
    return *this+(-v);
  }

  void operator*=(ll v){
    if(v<0) sign=-sign,v=-v;
    for(ll i=0,carry=0;i<(ll)a.size() or  carry;++i){
      if(i ==(ll)a.size()) a.emplace_back(0);
      ll cur=a[i] *(ll)v+carry;
      carry=(ll)(cur/base);
      a[i]=(ll)(cur%base);
      // asm("divl %%ecx" : "=a"(carry),"=d"(a[i]) : "A"(cur),"c"(base));
    }
    trim();
  }

  bigint operator*(ll v) const{
    bigint res=*this;
    res*=v;
    return res;
  }

  friend pair<bigint,bigint> divmod(const bigint &a1,const bigint &b1){
    ll norm=base/(b1.a.back()+1);
    bigint a=a1.abs()*norm;
    bigint b=b1.abs()*norm;
    bigint q,r;
    q.a.resize(a.a.size());

    for(ll i=a.a.size()-1;i>=0;i--){
      r *=base;
      r+=a.a[i];
      ll s1=r.a.size()<=b.a.size() ? 0 : r.a[b.a.size()];
      ll s2=r.a.size()<=b.a.size()-1 ? 0 : r.a[b.a.size()-1];
      ll d=((ll)base*s1+s2)/b.a.back();
      r-=b*d;
      while(r<0) r+=b,--d;
      q.a[i]=d;
    }

    q.sign=a1.sign*b1.sign;
    r.sign=a1.sign;
    q.trim();
    r.trim();
    return make_pair(q,r/norm);
  }

  bigint operator/(const bigint &v) const{
    return divmod(*this,v).first;
  }

  bigint operator%(const bigint &v) const{
    return divmod(*this,v).second;
  }

  void operator/=(ll v){
    if(v<0) sign=-sign,v=-v;
    for(ll i=(ll)a.size()-1,rem=0;i>=0;--i){
      ll cur=a[i]+rem *(ll)base;
      a[i]=(ll)(cur/v);
      rem=(ll)(cur%v);
    }
    trim();
  }

  bigint operator/(ll v) const{
    bigint res=*this;
    res/=v;
    return res;
  }

  ll operator%(ll v) const{
    if(v<0) v=-v;
    ll m=0;
    for(ll i=a.size()-1;i>=0;--i) m=(a[i]+m*(ll)base)%v;
    return m*sign;
  }

  void operator+=(const bigint &v){
    *this=*this+v;
  }

  void operator-=(const bigint &v){
    *this=*this-v;
  }

  void operator*=(const bigint &v){
    *this=*this*v;
  }

  void operator/=(const bigint &v){
    *this=*this/v;
  }

  bool operator<(const bigint &v) const{
    if(sign!=v.sign) return sign<v.sign;
    if(a.size()!=v.a.size()) return a.size()*sign<v.a.size()*v.sign;
    for(ll i=a.size()-1;i>=0;i--)
      if(a[i]!=v.a[i]) return a[i]*sign<v.a[i]*sign;
    return false;
  }

  bool operator>(const bigint &v) const{
    return v<*this;
  }

  bool operator<=(const bigint &v) const{
    return !(v<*this);
  }

  bool operator>=(const bigint &v) const{
    return !(*this<v);
  }

  bool operator==(const bigint &v) const{
    return !(*this<v) and !(v<*this);
  }

  bool operator!=(const bigint &v) const{
    return *this<v or v<*this;
  }

  void trim(){
    while(!a.empty() and !a.back()) a.pop_back();
    if(a.empty()) sign=1;
  }

  bool isZero() const{
    return a.empty() or (a.size()==1 and !a[0]);
  }

  bigint operator-() const{
    bigint res=*this;
    res.sign=-sign;
    return res;
  }

  bigint abs() const{
    bigint res=*this;
    res.sign*=res.sign;
    return res;
  }

  ll longValue() const{
    ll res=0;
    for(ll i=a.size()-1;i>=0;i--) res=res*base+a[i];
    return res*sign;
  }

  friend bigint gcd(const bigint &a,const bigint &b){
    return b.isZero()?a:gcd(b,a%b);
  }

  friend bigint lcm(const bigint &a,const bigint &b){
    return a/gcd(a,b)*b;
  }

  void read(const string &s){
    sign=1;
    a.clear();
    ll pos=0;
    while(pos<(ll)s.size() and (s[pos]=='-' or s[pos]=='+')){
      if(s[pos]=='-') sign=-sign;
      ++pos;
    }
    for(ll i=s.size()-1;i>=pos;i-=base_digits){
      ll x=0;
      for(ll j=max(pos,i-base_digits+1);j<=i;j++) x=x*10+s[j]-'0';
      a.emplace_back(x);
    }
    trim();
  }

  friend istream &operator>>(istream &stream,bigint &v){
    string s;
    stream>>s;
    v.read(s);
    return stream;
  }

  friend ostream &operator<<(ostream &stream,const bigint &v){
    if(v.sign==-1) stream<<'-';
    stream<<(v.a.empty()?0:v.a.back());
    for(ll i=(ll)v.a.size()-2;i>=0;--i)
      stream<<setw(base_digits)<<setfill('0')<<v.a[i];
    return stream;
  }

  static vll convert_base(const vll &a,ll old_digits,ll new_digits){
    vll p(max(old_digits,new_digits)+1);
    p[0]=1;
    for(ll i=1;i<(ll)p.size();i++) p[i]=p[i-1]*10;
    vll res;
    ll cur=0;
    ll cur_digits=0;
    for(ll i=0;i<(ll)a.size();i++){
      cur+=a[i]*p[cur_digits];
      cur_digits+=old_digits;
      while(cur_digits>=new_digits){
        res.emplace_back(signed(cur%p[new_digits]));
        cur/=p[new_digits];
        cur_digits-=new_digits;
      }
    }
    res.emplace_back((signed)cur);
    while(!res.empty() and !res.back()) res.pop_back();
    return res;
  }

  static vll karatsubaMultiply(vll &a,vll &b){
    {
      while(a.size()<b.size()) a.emplace_back(0);
      while(b.size()<a.size()) b.emplace_back(0);
      while(a.size()&(a.size()-1)) a.emplace_back(0),b.emplace_back(0);
    }

    ll n=a.size();
    vll res(n+n);
    if(n<=32){
      for(ll i=0;i<n;i++)
        for(ll j=0;j<n;j++)
          res[i+j]+=a[i]*b[j];
      return res;
    }

    ll k=n>>1;
    vll a1(a.begin(),a.begin()+k);
    vll a2(a.begin()+k,a.end());
    vll b1(b.begin(),b.begin()+k);
    vll b2(b.begin()+k,b.end());

    vll a1b1=karatsubaMultiply(a1,b1);
    vll a2b2=karatsubaMultiply(a2,b2);

    for(ll i=0;i<k;i++) a2[i]+=a1[i];
    for(ll i=0;i<k;i++) b2[i]+=b1[i];

    vll r=karatsubaMultiply(a2,b2);
    for(ll i=0;i<(ll)a1b1.size();i++) r[i]-=a1b1[i];
    for(ll i=0;i<(ll)a2b2.size();i++) r[i]-=a2b2[i];

    for(ll i=0;i<(ll)r.size();i++) res[i+k]+=r[i];
    for(ll i=0;i<(ll)a1b1.size();i++) res[i]+=a1b1[i];
    for(ll i=0;i<(ll)a2b2.size();i++) res[i+n]+=a2b2[i];
    return res;
  }

  bigint operator*(const bigint &v) const{
    constexpr static ll nbase = 10000;
    constexpr static ll nbase_digits = 4;

    vll a=convert_base(this->a,base_digits,nbase_digits);
    vll b=convert_base(v.a,base_digits,nbase_digits);

    if(a.empty() or b.empty()) return bigint(0);

    vll c=karatsubaMultiply(a,b);
    // vll c=FFT::multiply(a,b);

    bigint res;
    res.sign=sign*v.sign;
    for(ll i=0,carry=0;i<(ll)c.size();i++){
      ll cur=c[i]+carry;
      res.a.emplace_back((ll)(cur%nbase));
      carry=(ll)(cur/nbase);
      if(i+1==(int)c.size() and carry>0) c.emplace_back(0);
    }

    res.a=convert_base(res.a,nbase_digits,base_digits);
    res.trim();
    return res;
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 400, in update
    raise BundleErrorAt(path, i + 1, "unable to process #include in #if / #ifdef / #ifndef other than include guards")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: tools/bigint.cpp: line 6: unable to process #include in #if / #ifdef / #ifndef other than include guards
Back to top page