高精度模板：
颓了个很好的高精板子（但没有高精乘低精，以后再补）。
struct Big{
int len,s[810];
Big(){memset(s,0,sizeof(s)); len=1;}
Big(int val) {*this=val;}
Big(const char *val) {*this=val;}
Big operator = (const int &val){
R char s[810];
sprintf(s,"%d",val);
*this=s;return *this;
}
Big operator = (const char *val){
len=strlen(val);
while(len>1&&val[0]=='0') ++val,len--;
for(R int i=0;i<len;++i) s[i]=val[len-i-1]-'0';
return *this;
}
inline void deal(){
while(len>1&&!s[len-1]) len--;
}
Big operator + (const Big &a) const {
Big res; res.len=0;
R int top=max(len,a.len),add=0;
for(R int i=0;add||i<top;++i){
R int now=add;
if(i<len) now+=s[i];
if(i<a.len) now+=a.s[i];
res.s[res.len++]=now%10;
add=now/10;
}
return res;
}
Big operator - (const Big &a) const {
Big res; res.len=0;R int del=0;
for(R int i=0;i<len;++i){
R int now=s[i]-del;
if(i<a.len) now-=a.s[i];
if(now>=0) del=0;
else del=1,now+=10;
res.s[res.len++]=now;
}
res.deal(); return res;
}
Big operator * (const Big &a) const {
Big res; res.len=len+a.len;
for(R int i=0;i<len;++i)
for(R int j=0;j<a.len;++j)
res.s[i+j]+=s[i]*a.s[j];
for(R int i=0;i<res.len;++i)
res.s[i+1]+=res.s[i]/10,res.s[i]%=10;
res.deal(); return res;
}
Big operator / (const Big &a) const {
Big res,cur=0;res.len=len;
for(R int i=len-1;~i;--i){
cur=cur*10,cur.s[0]=s[i];
while(cur>=a)
cur-=a,res.s[i]++;
}
res.deal(); return res;
}
Big operator % (const Big &a) const {
Big res=*this/a;
return *this-res*a;
}
Big operator += (const Big &a) {*this=*this+a; return *this;}
Big operator -= (const Big &a) {*this=*this-a; return *this;}
Big operator *= (const Big &a) {*this=*this*a; return *this;}
Big operator /= (const Big &a) {*this=*this/a; return *this;}
Big operator %= (const Big &a) {*this=*this%a; return *this;}
bool operator < (const Big &a) const {
if(len!=a.len) return len<a.len;
for(R int i=len-1;~i;i--)
if(s[i]!=a.s[i]) return s[i]<a.s[i];
return false;
}
bool operator > (const Big &a) const {return a<*this;}
bool operator <= (const Big &a) const {return !(*this>a);}
bool operator >= (const Big &a) const {return !(*this<a);}
bool operator == (const Big &a) const {return !(*this>a||*this<a);}
bool operator != (const Big &a) const {return *this>a||*this<a;}
inline void print(){
for(R int i=a.len-1;~i;--i)
printf("%d",a.s[i]); puts("");
}
};
struct bigint{
int a[300];
int& operator [](int x){ return a[x]; }
inline void init(){ memset(a,0,sizeof(a)); }
inline void build(ll x){ int len=0; while(x) a[++len]=x%10,x/=10; a[0]=len; }
friend bool operator >=(bigint x,bigint y){
if(x[0]>y[0])return 1;
if(x[0]<y[0])return 0;
for(R int i=x[0];i>=1;--i){
if(x[i]>y[i])return 1;
if(x[i]<y[i])return 0;
}
return 1;
}
friend bool operator ==(bigint x,bigint y){
if(x[0]!=y[0])return 0;
for(R int i=x[0];i>=1;--i)
if(x[i]!=y[i])return 0;
return 1;
}
friend bigint operator +(bigint x,bigint y){
int len=max(x[0],y[0])+1;
bigint z;z.init();
for(R int i=1;i<=len;++i)z[i]=x[i]+y[i];
for(R int i=1;i<=len;++i)z[i+1]+=z[i]/10,z[i]%=10;
while(len>1&&z[len]==0)--len;z[0]=len;
return z;
}
friend bigint operator +(bigint x,int y){
bigint z;z.build(y);z=x+z;return z;
}
friend bigint operator -(bigint x,bigint y){
if(x==y){ x.init();x[0]=1;return x; }
for(R int i=1;i<=x[0];++i){
if(x[i]<y[i]) --x[i+1],x[i]+=10;
x[i]-=y[i];
}
while(x[0]>1&&x[x[0]]==0)--x[0];
return x;
}
friend bigint operator -(bigint x,int y){
bigint z;z.build(y); z=x-z;return z;
}
friend bigint operator *(bigint x,bigint y){
int len=x[0]+y[0]+1;
bigint z;z.init();
for(R int i=1;i<=y[0];++i)
for(R int j=1;j<=x[0];++j)
z[i+j-1]+=y[i]*x[j];
for(R int i=1;i<=len;++i)
z[i+1]+=z[i]/10,z[i]%=10;
while(len>1&&z[len]==0)--len;z[0]=len;
return z;
}
friend bigint operator /(bigint x,bigint y){
int len=x[0]-y[0]+1;
bigint z,m;z.init();m.init();
for(R int i=len;i>=1;--i){
m.init(); m[0]=y[0]+i-1;
for(R int j=1;j<=y[0];++j) m[j+i-1]=y[j];
while(x>=m) ++z[i],x=x-m;
}
while(len>1&&z[len]==0)--len;z[0]=len;
return z;
}
friend bigint operator /(bigint x,int y){
bigint z;z.build(y); z=x/z;return z;
}
friend bigint operator %(bigint x,bigint y){
bigint z;z=x/y; z=z*y; z=x-z;return z;
}
inline void print(){
for(R int i=a[0];i;--i)
printf("%d",a[i]);puts("");
return;
}
};