当遇到一道题数据爆long long时,先写出小范围数据的算法模板,之后再根据需要用高精度数据的地方进行修改,可以减少失误。
update at 2019.3.6
代码如下
struct bint{
#define mod 10000
long long t[1010];int len;
bint():len(0){memset(t,0,sizeof(t));}
bint(int val){t[1]=val,rebuild();}
inline long long& operator[](int i){return t[i];}
inline void rebuild(){
for(int i=1;i<=len;i++)t[i+1]+=t[i]/mod,t[i]%=mod;
while(t[len+1])++len,t[len+1]+=t[len]/mod,t[len]%=mod;
}
bint operator*(int val){
bint z=*this;
for(int i=1;i<=z.len;i++)z[i]*=val;
return z.rebuild(),z;
}
bint operator/(int val){
bint z;
long long now=0,ans=0;bool flag=0;
for(int i=len;i;i--){
now=now*mod+t[i];
ans=now/val,now%=val;
if(!ans&&!flag)continue;
else z[++z.len]=ans,flag=1;
}
return reverse(z.t+1,z.t+z.len+1),z;
}
friend bint max(bint a,bint b){
if(a.len!=b.len)return a.len<b.len?b:a;
for(int i=a.len;i;i--)if(a[i]!=b[i])return a[i]<b[i]?b:a;
return a;
}
void print(){
printf("%lld",t[len]);
for(int i=len-1;i;i--)printf("%04lld",t[i]);
puts("");
}
};
#include <bits/stdc++.h>
using namespace std;
struct big_integer{
#define mod 10
#define maxn 5010
int t[maxn],len;
big_integer():len(0){memset(t,0,sizeof(t));}
inline void rebuild(){
for(int i=1;i<=len;i++)t[i+1]+=t[i]/mod,t[i]%=mod;
while(t[len+1])++len,t[len+1]+=t[len]/mod,t[len]%=mod;
while(!t[len])--len;
}
inline void rebuild2(){
for(int i=1;i<=len;i++)if(t[i]<0)t[i]+=mod,--t[i+1];
while(!t[len])--len;
}
inline int& operator[](int i){return this->t[i];}
inline void operator=(int val){this->t[1]=val,this->rebuild();}
inline void operator=(string& s){
this->len=0;
for(int i=s.size()-1;i>=0;i--)t[++len]=s[i]-'0';
}
friend big_integer operator+(big_integer& x,big_integer& y){
big_integer z;
z.len=max(x.len,y.len);
for(int i=1;i<=z.len;i++)z[i]=x[i]+y[i];
z.rebuild();
return z;
}
friend big_integer operator-(big_integer& x,big_integer& y){
big_integer z;
z.len=max(x.len,y.len);
for(int i=1;i<=z.len;i++)z[i]=x[i]-y[i];
z.rebuild2();
return z;
}
friend big_integer operator*(big_integer& x,big_integer &y){
big_integer z;
z.len=x.len+y.len-1;
for(int i=1;i<=x.len;i++)
for(int j=1;j<=y.len;j++)
z[i+j-1]+=x[i]*y[j];
z.rebuild();
return z;
}
friend bool operator<(big_integer& x,big_integer& y){
if(x.len!=y.len)return x.len<y.len;
for(int i=x.len;i>=1;i--)if(x.t[i]!=y[i])return x.t[i]<y[i];
return 0;
}
inline void print(){
printf("%d",this->t[len]);
for(int i=len-1;i>=1;i--)printf("%d",this->t[i]);
putchar('
');
}
};