API tools faq
paste
Advertisement
Guest User

BigInt

a guest
Apr 12th, 2013
536
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.65 KB | None | 0 0
raw download clone embed print report
  1. #include <vector>
  2. #include <cstdlib>
  3. #include <cctype>
  4. #include <cstring>
  5. #include <sstream>
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <cmath>
  9. #include <climits>
  10.  
  11. using namespace std;
  12.  
  13.  
  14. typedef long long ll;
  15. typedef long double ld;
  16. typedef unsigned long long ull;
  17. typedef unsigned int uint;
  18.  
  19. #ifdef _MSC_VER
  20.     const ld M_PI=(ld)3.1415926535897932384626433832795;
  21. #endif
  22.  
  23.  
  24. namespace Numbers
  25. {      
  26.     void clear(vector <int>&);  //for GNU C++
  27.  
  28.     class Lint
  29.     {
  30.     private:
  31.         static const int base=1e6;
  32.         static const int LOG_BASE=6;
  33.         static const int BIG_NUM_SZ=1e6;
  34.         static const Lint ONE;
  35.  
  36.         vector <int> v;
  37.         bool sgn;
  38.     public:
  39.         Lint()
  40.         {
  41.             sgn=false;
  42.         }
  43.         Lint(int a)
  44.         {
  45.             char s[12];
  46.             sprintf(s,"%d",a);
  47.             init(s);
  48.         }
  49.         Lint(unsigned int a)
  50.         {
  51.             char s[12];
  52.             sprintf(s,"%u",a);
  53.             init(s);
  54.         }
  55.         Lint(ll a)
  56.         {
  57.             string s;
  58.             stringstream tmp;
  59.             tmp<<a;
  60.             tmp>>s;
  61.             init(s);
  62.         }
  63.         Lint(ull a)
  64.         {
  65.             string s;
  66.             stringstream tmp;
  67.             tmp<<a;
  68.             tmp>>s;
  69.             init(s);
  70.         }
  71.         Lint(const char* s)
  72.         {
  73.             init(s);
  74.         }
  75.         Lint(const string& s)
  76.         {
  77.             init(s);
  78.         }
  79.         void swap(Lint &b)
  80.         {
  81.             std::swap(sgn,b.sgn);
  82.             v.swap(b.v);
  83.         }
  84.        
  85.         /*operator bool()
  86.         {
  87.             return !is_null();
  88.         }*/
  89.         Lint operator -()
  90.         {
  91.             sgn^=true;
  92.             if (is_null())
  93.                 sgn=false;
  94.             return *this;
  95.         }
  96.         Lint& operator +=(Lint b)
  97.         {
  98.             if (!(sgn^b.sgn))
  99.                 this->add(b);
  100.             else
  101.             {
  102.                 int res=this->cmp(b);
  103.                 if (sgn && !b.sgn)
  104.                 {
  105.                     if (res<=0)
  106.                     {
  107.                         this->swap(b);
  108.                         this->sub(b);
  109.                         sgn=false;
  110.                     } else                 
  111.                         this->sub(b);                                      
  112.                 } else
  113.                 {
  114.                     if (res>=0)
  115.                         this->sub(b);
  116.                     else
  117.                     {
  118.                         this->swap(b);
  119.                         this->sub(b);
  120.                         sgn=true;
  121.                     }
  122.                 }
  123.             }
  124.             return *this;
  125.         }
  126.         Lint& operator -=(Lint b)
  127.         {
  128.             int res=this->cmp(b);
  129.             if (!sgn && !b.sgn)
  130.             {
  131.                 if (res>=0)
  132.                     this->sub(b);
  133.                 else
  134.                 {
  135.                     this->swap(b);
  136.                     this->sub(b);
  137.                     sgn=true;
  138.                 }
  139.             } else if (sgn && b.sgn)
  140.             {
  141.                 if (res<=0)
  142.                 {
  143.                     this->swap(b);
  144.                     this->sub(b);
  145.                     sgn=false;
  146.                 } else
  147.                     this->sub(b);
  148.             } else if (sgn || b.sgn)       
  149.                 this->add(b);          
  150.             return *this;
  151.         }
  152.         Lint& operator *=(const Lint& b)
  153.         {
  154.             if (len()*1ll*b.len()>=BIG_NUM_SZ)
  155.                 this->fast_mul(b);
  156.             else
  157.                 this->mul(b);
  158.             sgn^=b.sgn;
  159.             if (is_null())
  160.                 sgn=false;
  161.             return *this;
  162.         }      
  163.         Lint& operator /=(const Lint& b)
  164.         {
  165.             bool res=(sgn^b.sgn);
  166.             Lint c,d;
  167.             this->div_mod(b,c,d);          
  168.             this->swap(c);
  169.             sgn=res;
  170.             if (is_null())
  171.                 sgn=false;
  172.             return *this;
  173.         }
  174.         Lint& operator %=(const Lint& b)
  175.         {                      
  176.             Lint c,d;
  177.             this->div_mod(b,c,d);          
  178.             this->swap(d);
  179.             if (sgn)
  180.                 *this+=b;  
  181.             sgn=false;
  182.             return *this;
  183.         }      
  184.         Lint& operator +=(ll b)
  185.         {
  186.             return *this+=Lint(b);
  187.         }
  188.         Lint& operator -=(ll b)
  189.         {
  190.             return *this-=Lint(b);
  191.         }  
  192.         Lint& operator *=(ll b)
  193.         {
  194.             return *this*=Lint(b);
  195.         }  
  196.         Lint& operator /=(ll b)
  197.         {
  198.             ll tmp=(1ll<<63);          
  199.             if (b!=tmp && b<base && -b<base)
  200.             {
  201.                 uint r;            
  202.                 this->short_div_mod((uint)(b<0?-b:b),r);
  203.                 sgn^=(b<0);
  204.                 if (is_null())
  205.                     sgn=false;
  206.                 return *this;
  207.             } else
  208.                 return *this/=Lint(b);
  209.         }  
  210.         Lint& operator %=(ll b)
  211.         {
  212.             ll tmp=(1ll<<63);          
  213.             if (b!=tmp && b<base && -b<base)
  214.             {
  215.                 uint r;            
  216.                 this->short_div_mod((uint)(b<0?-b:b),r);
  217.                 clear(v);              
  218.                 if (sgn)
  219.                     v.push_back(r+b);
  220.                 else
  221.                     v.push_back(r);
  222.                 sgn=false;
  223.                 return *this;
  224.             } else
  225.                 return *this%=Lint(b);
  226.         }      
  227.         Lint& operator ++()
  228.         {
  229.             return *this+=ONE;
  230.         }
  231.         Lint operator ++(int)
  232.         {
  233.             Lint a=*this;
  234.             *this+=ONE;
  235.             return a;
  236.         }
  237.         Lint& operator --()
  238.         {
  239.             return *this-=ONE;
  240.         }
  241.         Lint operator --(int)
  242.         {
  243.             Lint a=*this;
  244.             *this-=ONE;
  245.             return a;
  246.         }
  247.         friend Lint operator +(const Lint&,const Lint&);
  248.         friend Lint operator -(const Lint&,const Lint&);
  249.         friend Lint operator *(const Lint&,const Lint&);   
  250.         friend Lint operator /(const Lint&,const Lint&);
  251.         friend Lint operator %(const Lint&,const Lint&);
  252.         friend Lint operator /(const Lint&,ll);
  253.         friend Lint operator %(const Lint&,ll);
  254.         friend bool operator <(const Lint&,const Lint&);
  255.         friend bool operator ==(const Lint&,const Lint&);
  256.         friend bool operator >(const Lint&,const Lint&);
  257.         friend bool operator !=(const Lint&,const Lint&);
  258.         friend bool operator <=(const Lint&,const Lint&);
  259.         friend bool operator >=(const Lint&,const Lint&);      
  260.         friend istream& operator >>(istream&,Lint&);
  261.         friend ostream& operator <<(ostream&,const Lint&);         
  262.  
  263.         string std_str() const
  264.         {
  265.             string ans;
  266.             char buf[10],form[10];
  267.             sprintf(form,"%%0%dd",LOG_BASE);
  268.             if (sgn)
  269.                 ans+='-';
  270.             sprintf(buf,"%d",v.empty()?0:v.back());
  271.             ans+=buf;
  272.             for(int i=(int)len()-2;i>=0;i--)
  273.             {
  274.                 sprintf(buf,form,v[i]);
  275.                 ans+=buf;
  276.             }
  277.             return ans;
  278.         }
  279.         const char* c_str() const
  280.         {
  281.             return this->std_str().c_str();
  282.         }      
  283.  
  284.     private:       
  285.         class Complex
  286.         {
  287.         private:
  288.             ld r,i;
  289.         public:
  290.             Complex()
  291.             {
  292.                 r=i=0.0;
  293.             }      
  294.             Complex(ld x,ld y=0): r(x),i(y) {}                             
  295.             Complex& operator =(int a)
  296.             {
  297.                 r=a;
  298.                 i=0;
  299.                 return *this;
  300.             }                          
  301.             ld imag() const
  302.             {
  303.                 return i;
  304.             }
  305.             ld real() const
  306.             {
  307.                 return r;
  308.             }  
  309.             Complex& operator +=(Complex& b)
  310.             {
  311.                 r+=b.r;
  312.                 i+=b.i;
  313.                 return *this;
  314.             }
  315.             Complex& operator -=(Complex& b)
  316.             {
  317.                 r-=b.r;
  318.                 i-=b.i;
  319.                 return *this;
  320.             }
  321.             Complex& operator *=(Complex& b)
  322.             {
  323.                 ld t=r;
  324.                 r=r*b.r-i*b.i;
  325.                 i=t*b.i+b.r*i;
  326.                 return *this;
  327.             }  
  328.             Complex& operator /=(ld b)
  329.             {
  330.                 r/=b;
  331.                 i/=b;
  332.                 return *this;
  333.             }
  334.             Complex operator -(Complex b)
  335.             {
  336.                 Complex c=*this;
  337.                 return c-=b;
  338.             }
  339.             Complex operator +(Complex b)
  340.             {
  341.                 Complex c=*this;
  342.                 return c+=b;
  343.             }
  344.             Complex operator *(Complex b)
  345.             {
  346.                 Complex c=*this;
  347.                 return c*=b;
  348.             }
  349.         };             
  350.         friend void fft(vector <Complex>&,bool);
  351.  
  352.         uint len() const
  353.         {
  354.             return v.size();
  355.         }
  356.         int cmp(const Lint& b) const
  357.         {
  358.             if (is_null() && b.is_null())
  359.                 return 0;
  360.             if (len()<b.len())
  361.                 return -1;
  362.             else if (len()>b.len())
  363.                 return 1;
  364.             for(int i=(int)len()-1;i>=0;i--)
  365.                 if (v[i]<b.v[i])
  366.                     return -1;
  367.                 else if (v[i]>b.v[i])
  368.                     return 1;
  369.             return 0;
  370.         }      
  371.         void init(const string& s)
  372.         {          
  373.             int st=0;
  374.             if (s[0]=='-')
  375.             {
  376.                 sgn=true;
  377.                 st=1;
  378.             } else
  379.                 sgn=false;
  380.             clear(v);
  381.             for(int i=s.size();i>st;i-=LOG_BASE)
  382.             {
  383.                 int cur,l,r;
  384.                 if (i-st>=LOG_BASE)
  385.                 {
  386.                     l=i-LOG_BASE;
  387.                     r=LOG_BASE;
  388.                 } else
  389.                 {
  390.                     l=st;
  391.                     r=i-st;
  392.                 }      
  393.                 cur=atoi(s.substr(l,r).c_str());
  394.                 if (!cur)
  395.                 {
  396.                     bool ok=true;
  397.                     for(int j=l;j<l+r && ok;j++)
  398.                         if (!isdigit(s[j]))
  399.                             ok=false;
  400.                     if (!ok) ; //error: not a number
  401.                 }
  402.                 v.push_back(cur);
  403.             }
  404.             if (is_null())
  405.                 sgn=false;         
  406.         }
  407.         bool is_null() const
  408.         {
  409.             return v.empty() || v.size()==1 && v.back()==0;
  410.         }
  411.  
  412.         void add(const Lint& b)
  413.         {
  414.             int r=0;
  415.             for(int i=0;i<max(len(),b.len()) || r;i++)
  416.             {
  417.                 if (i==len())
  418.                     v.push_back(0);
  419.                 v[i]+=r+(i<b.len()?b.v[i]:0);
  420.                 r=v[i]>=base;
  421.                 if (r)
  422.                     v[i]-=base;
  423.             }
  424.         }
  425.         void sub(const Lint& b)
  426.         {
  427.             int r=0;
  428.             for(int i=0;i<b.len() || r;i++)
  429.             {
  430.                 v[i]-=(r+(i<b.len()?b.v[i]:0));
  431.                 r=v[i]<0;
  432.                 if (r)
  433.                     v[i]+=base;
  434.             }
  435.             while (len()>1 && v.back()==0)
  436.                 v.pop_back();
  437.         }  
  438.         void mul(const Lint& b)
  439.         {
  440.             vector <int> c(len()+b.len());     
  441.             for(int i=0;i<len();i++)
  442.                 for(int j=0,r=0;j<b.len() || r;j++)
  443.                 {
  444.                     ll cur=c[i+j]+v[i]*1ll*(j<b.len()?b.v[j]:0)+r;
  445.                     c[i+j]=cur%base;
  446.                     r=cur/base;
  447.                 }
  448.             while (c.size()>1 && c.back()==0)
  449.                 c.pop_back();
  450.             v=c;
  451.         }
  452.         void fast_mul(const Lint& b)
  453.         {
  454.             int n=1;
  455.             while (n<max(len(),b.len()))
  456.                 n<<=1;
  457.             n<<=1;
  458.             vector <Complex> a1(n),a2(n);          
  459.             copy(v.begin(),v.end(),a1.begin());
  460.             copy(b.v.begin(),b.v.end(),a2.begin());        
  461.             if (!len())    
  462.                 a1.push_back(0);
  463.             if (!b.len())
  464.                 a2.push_back(0);           
  465.             fft(a1,false);
  466.             fft(a2,false);
  467.             for(int i=0;i<n;i++)
  468.                 a1[i]*=a2[i];
  469.             fft(a1,true);                      
  470.             v.resize(n);
  471.             for(int i=0,r=0;i<n;i++)
  472.             {
  473.                 ll cur=(ll)(a1[i].real()+0.5)+r;               
  474.                 v[i]=cur%base;
  475.                 r=cur/base;
  476.             }
  477.             while (len()>1 && v.back()==0)
  478.                 v.pop_back();
  479.         }      
  480.         void div_mod(const Lint& b,Lint& c,Lint& cur)
  481.         {          
  482.             c.v.resize(len());             
  483.             for(int i=(int)len()-1;i>=0;i--)
  484.             {                      
  485.                 cur.v.insert(cur.v.begin(),v[i]);
  486.                 while (cur.len()>1 && cur.v.back()==0)
  487.                     cur.v.pop_back();
  488.                 int l=0,r=base;
  489.                 while (l<r-1)
  490.                 {
  491.                     int m=(l+r)>>1;
  492.                     Lint tmp=b;                
  493.                     tmp.mul(Lint(m));                              
  494.                     if (tmp.cmp(cur)<=0)
  495.                         l=m;
  496.                     else
  497.                         r=m;
  498.                 }
  499.                 c.v[i]=l;
  500.                 Lint tmp=b;
  501.                 tmp*=l;
  502.                 cur-=tmp;
  503.             }
  504.             while (c.len()>1 && c.v.back()==0)
  505.                 c.v.pop_back();        
  506.         }
  507.         void short_div_mod(uint b,uint& cur)
  508.         {
  509.             cur=0;
  510.             for(int i=(int)len()-1;i>=0;i--)
  511.             {
  512.                 ll tmp=v[i]+cur*1ll*base;
  513.                 v[i]=tmp/b;
  514.                 cur=tmp%b;
  515.             }
  516.             while (len()>1 && v.back()==0)
  517.                 v.pop_back();
  518.         }
  519.     };
  520.  
  521.     const Lint Lint::ONE=1;
  522.        
  523.     void clear(vector <int>& a)
  524.     {
  525.         vector <int> tmp;
  526.         a.swap(tmp);
  527.     }
  528.     void fft(vector <Lint::Complex>& a,bool inv)
  529.     {
  530.         int n=a.size();
  531.         if (n==1)
  532.             return;
  533.         ld ang=2*M_PI/n*(inv?-1:1);
  534.         Lint::Complex wn=Lint::Complex(cos(ang),sin(ang)),w=1;
  535.         vector <Lint::Complex> a0(n/2),a1(n/2);
  536.         for(int i=0,j=0;i<n;i+=2,j++)
  537.         {
  538.             a0[j]=a[i];
  539.             a1[j]=a[i+1];
  540.         }
  541.         fft(a0,inv);
  542.         fft(a1,inv);
  543.         for(int i=0;i<n/2;i++)
  544.         {
  545.             a[i]=a0[i]+w*a1[i];
  546.             a[i+n/2]=a0[i]-w*a1[i];
  547.             w*=wn;
  548.             if (inv)
  549.             {
  550.                 a[i]/=2;
  551.                 a[i+n/2]/=2;
  552.             }
  553.         }
  554.     }
  555.  
  556.     Lint operator +(const Lint& a,const Lint& b)
  557.     {
  558.         Lint tmp=a;
  559.         return tmp+=b;
  560.     }
  561.     Lint operator -(const Lint& a,const Lint& b)
  562.     {
  563.         Lint tmp=a;
  564.         return tmp-=b;
  565.     }
  566.     Lint operator *(const Lint& a,const Lint& b)
  567.     {
  568.         Lint tmp=a;
  569.         return tmp*=b;
  570.     }
  571.     Lint operator /(const Lint& a,const Lint& b)
  572.     {
  573.         Lint tmp=a;
  574.         return tmp/=b;
  575.     }
  576.     Lint operator %(const Lint& a,const Lint& b)
  577.     {
  578.         Lint tmp=a;
  579.         return tmp%=b;
  580.     }
  581.     Lint operator /(const Lint& a,ll b)
  582.     {
  583.         Lint tmp=a;
  584.         return tmp/=b;
  585.     }
  586.     Lint operator %(const Lint& a,ll b)
  587.     {
  588.         Lint tmp=a;
  589.         return tmp%=b;
  590.     }
  591.     bool operator <(const Lint& a,const Lint& b)
  592.     {
  593.         bool cod=false;
  594.         if (a.is_null() && b.is_null())
  595.             return false;
  596.         if (a.sgn && !b.sgn)
  597.             return true;
  598.         else if (!a.sgn && b.sgn)
  599.             return false;
  600.         else if (a.sgn && b.sgn)
  601.             cod=true;
  602.         if (a.len()<b.len())
  603.             return cod^1;
  604.         else if (a.len()>b.len())
  605.             return cod;
  606.         for(int i=(int)a.len()-1;i>=0;i--)
  607.             if (a.v[i]<b.v[i])
  608.                 return cod^1;
  609.             else if (a.v[i]>b.v[i])
  610.                 return cod;
  611.         return false;
  612.     }
  613.     bool operator ==(const Lint& a,const Lint& b)
  614.     {
  615.         if (a.is_null() && b.is_null())
  616.             return true;
  617.         if (a.sgn!=b.sgn || a.len()!=b.len())
  618.             return false;
  619.         for(int i=0;i<a.len();i++)
  620.             if (a.v[i]!=b.v[i])
  621.                 return false;
  622.         return true;
  623.     }
  624.     bool operator <=(const Lint& a,const Lint& b)
  625.     {
  626.         return a<b || a==b;
  627.     }
  628.     bool operator >(const Lint& a,const Lint& b)
  629.     {
  630.         return !(a<=b);
  631.     }
  632.     bool operator >=(const Lint& a,const Lint& b)
  633.     {
  634.         return !(a<b);
  635.     }
  636.     bool operator !=(const Lint& a,const Lint& b)
  637.     {
  638.         return !(a==b);
  639.     }
  640.     istream& operator >>(istream& in,Lint& a)
  641.     {
  642.         string s;
  643.         in>>s;
  644.         a.init(s);
  645.         return in;
  646.     }
  647.     ostream& operator <<(ostream& out,const Lint& a)
  648.     {
  649.         string s=a.std_str();
  650.         out<<s;
  651.         return out;
  652.     }
  653. };
  654.  
  655. typedef Numbers::Lint Lint;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!