1 #include <iostream>
  2 #include <cstring>
  3 #include <string>
  4 #include <vector>
  5 #include <set>
  6 #include <cstdio>
  7 #include <algorithm>
  8 using namespace std;
  9 typedef long long LL;
 10 
 11 
 12 struct Bign
 13 {
 14     static const int BASE=100000000;
 15     static const int WIDTH=8;
 16     vector<int>s;
 17 
 18     Bign(LL n=0){*this=n;}
 19     Bign(const string& str){*this=str;}
 20     Bign operator =(LL n)
 21     {
 22         s.clear();
 23         do
 24         {
 25             s.push_back(n%BASE);
 26             n/=BASE;
 27         }while(n>0);
 28         return *this;
 29     }
 30     Bign operator =(const string& str)
 31     {
 32         s.clear();
 33         int x,len=(str.length()-1)/WIDTH+1;
 34         for(int i=0;i<len;i++)
 35         {
 36             int end=str.length()-i*WIDTH;
 37             int start=max(0,end-WIDTH);
 38             sscanf(str.substr(start,end-start).c_str(),"%d",&x);
 39             s.push_back(x);
 40         }
 41         return *this;
 42     }
 43     Bign operator +(const Bign& b)const
 44     {
 45         int len1=s.size(),len2=b.s.size();
 46         int len=max(len1,len2);
 47         int ans=0;
 48         Bign c;c.s.clear();
 49         for(int i=0;i<len||ans!=0;i++)
 50         {
 51             if(i<len1) ans+=s[i];
 52             if(i<len2) ans+=b.s[i];
 53             c.s.push_back(ans%BASE);
 54             ans/=BASE;
 55         }
 56         return c;
 57     }
 58     Bign operator -(const Bign& b)const
 59     {
 60 
 61         int len1=s.size(),len2=b.s.size();
 62         Bign c;c.s.clear();
 63         int ans=0,t=0;
 64         for(int i=0;i<len1;i++)
 65         {
 66             if(i<len2) ans=s[i]-b.s[i]+t;
 67             else ans=s[i]+t;
 68             if(ans<0)
 69             {
 70                 ans+=BASE;t=-1;
 71             }
 72             else t=0;
 73             if(ans>0)c.s.push_back(ans);
 74         }
 75         return c;
 76     }
 77     Bign operator *(const Bign& b)const
 78     {
 79         Bign c;
 80         int len1=s.size(),len2=b.s.size();
 81         for(int i=0;i<len2;i++)
 82         {
 83             for(int j=0;j<len1;j++)
 84             {
 85                 Bign ans=(LL)b.s[i]*s[j];
 86                 for(int k=0;k<i+j;k++)
 87                 ans.s.insert(ans.s.begin(),0);
 88                 c=c+ans;
 89             }
 90         }
 91         return c;
 92     }
 93 
 94     bool operator <(const Bign& b)const
 95     {
 96         if(s.size()!=b.s.size()) return s.size()<b.s.size();
 97         for(int i=s.size()-1;i>=0;i--)
 98             if(s[i]!=b.s[i]) return s[i]<b.s[i];
 99         return false;
100     }
101     bool operator ==(const Bign& b)const
102     {
103         if(s.size()!=b.s.size()) return false;
104         for(int i=s.size()-1;i>=0;i--)
105             if(s[i]!=b.s[i]) return false;
106         return true;
107     }
108 };
109 ostream& operator <<(ostream& out,const Bign& a)
110 {
111     out<<a.s.back();
112     char buf[10];
113     int len=a.s.size();
114     for(int i=len-2;i>=0;i--)
115     {
116         sprintf(buf,"%08d",a.s[i]);
117         out<<buf;
118     }
119     return out;
120 }
121 LL BtoL(const Bign& a)
122 {
123     LL c;
124     char buf[10];
125     string ss="";
126     int len=a.s.size();
127     sprintf(buf,"%d",a.s.back());ss+=(string)buf;
128     for(int i=len-2;i>=0;i--)
129     {
130         sprintf(buf,"%08d",a.s[i]);
131         ss+=(string)buf;
132     }
133     sscanf(ss.c_str(),"%lld",&c);
134     return c;
135 }
136 istream& operator >>(istream& in,Bign& a)
137 {
138     string s;
139     in>>s;
140     a=s;
141     return in;
142 }