高精度大全
高精加法:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2000;
const int base=10000;
char a[maxn],b[maxn];
struct bigint
{
int cnt;
ll a[maxn];
bigint(){cnt=0;memset(a,0,sizeof(a));}
inline void clear(){while(!a[cnt]&&cnt>1)cnt--;}//清除前导0
inline void print()//输出
{
printf("%lld",a[cnt]);
for(int i=cnt-1;i;i--)printf("%04lld",a[i]);
puts("");
}
inline void init2(ll x)//用long long赋值
{
cnt=0;memset(a,0,sizeof(a));
while(x)a[++cnt]=x%base,x/=base;
}
inline void init2(char* s)//用字符串赋值
{
cnt=1;memset(a,0,sizeof(a));
int len=strlen(s+1);
for(int i=len,j=1;i;i--)
{
if(j==base)j=1,cnt++;
a[cnt]+=(s[i]-'0')*j;j*=10;
}
}
}A,B,C;
bigint operator +(bigint x,bigint y)//高精加
{
bigint res;res.cnt=max(x.cnt,y.cnt);
ll k=0ll;
for(int i=1;i<=res.cnt;i++)
{
res.a[i]=x.a[i]+y.a[i]+k;
k=res.a[i]/base;
res.a[i]%=base;
}
if(k)res.a[++res.cnt]=k;
return res;
}
int main()
{
scanf("%s%s",a+1,b+1);
A.init2(a),B.init2(b);
//A.print();B.print();
C=A+B;
C.print();
return 0;
}
高精减法:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200000;
const int base=10000;
char a[maxn],b[maxn];
struct bigint
{
int cnt;
ll a[maxn];
bigint(){cnt=0;memset(a,0,sizeof(a));}
inline void clear(){while(!a[cnt]&&cnt>1)cnt--;}
inline void print()
{
printf("%lld",a[cnt]);
for(int i=cnt-1;i;i--)printf("%04lld",a[i]);
puts("");
}
inline void init2(ll x)
{
cnt=0;memset(a,0,sizeof(a));
while(x)a[++cnt]=x%base,x/=base;
}
inline void init2(char* s)
{
cnt=1;memset(a,0,sizeof(a));
int len=strlen(s+1);
for(int i=len,j=1;i;i--)
{
if(j==base)j=1,cnt++;
a[cnt]+=(s[i]-'0')*j;j*=10;
}
}
bool operator<(const bigint& x)const
{
if(cnt==x.cnt)
{
int i;
for(i=cnt;a[i]==x.a[i]&&i>1;i--);
if(i>=1)return a[i]<x.a[i];
else return 0;
}
else return cnt<x.cnt;
}
}A,B,C;
bigint operator-(bigint x,bigint y)
{
if(x<y)putchar('-'),swap(x,y);
bigint res=x;int len=x.cnt;
for(int i=1;i<=len;i++)
{
res.a[i]-=y.a[i];
if(res.a[i]<0)res.a[i+1]--,res.a[i]+=base;
}
res.clear();
return res;
}
int main()
{
scanf("%s%s",a+1,b+1);
A.init2(a),B.init2(b);
//A.print();B.print();
C=A-B;
C.print();
return 0;
}
高精乘法:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200000;
const int base=10000;
char a[maxn],b[maxn];
struct bigint
{
int cnt;
ll a[maxn];
bigint(){cnt=0;memset(a,0,sizeof(a));}
inline void clear(){while(!a[cnt]&&cnt>1)cnt--;}
inline void print()
{
printf("%lld",a[cnt]);
for(int i=cnt-1;i;i--)printf("%04lld",a[i]);
puts("");
}
inline void init2(ll x)
{
cnt=0;memset(a,0,sizeof(a));
while(x)a[++cnt]=x%base,x/=base;
}
inline void init2(char* s)
{
cnt=1;memset(a,0,sizeof(a));
int len=strlen(s+1);
for(int i=len,j=1;i;i--)
{
if(j==base)j=1,cnt++;
a[cnt]+=(s[i]-'0')*j;j*=10;
}
}
}A,B,C;
bigint operator*(bigint x,bigint y)
{
bigint res;res.cnt=x.cnt+y.cnt;
for(int i=1;i<=x.cnt;i++)
for(int j=1;j<=y.cnt;j++)
{
res.a[i+j-1]+=x.a[i]*y.a[j];
res.a[i+j]+=res.a[i+j-1]/base;
res.a[i+j-1]%=base;
}
res.clear();
return res;
}
int main()
{
scanf("%s%s",a+1,b+1);
A.init2(a),B.init2(b);
//A.print();B.print();
C=A*B;
C.print();
return 0;
}
高精除低精:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200000;
const int base=10000;
int k;
char s[maxn];
struct bigint
{
int cnt;
ll a[maxn];
bigint(){cnt=0;memset(a,0,sizeof(a));}
inline void clear(){while(!a[cnt]&&cnt>1)cnt--;}
inline void print()
{
printf("%lld",a[cnt]);
for(int i=cnt-1;i;i--)printf("%04lld",a[i]);
puts("");
}
inline void init2(ll x)
{
cnt=0;memset(a,0,sizeof(a));
while(x)a[++cnt]=x%base,x/=base;
}
inline void init2(char* s)
{
cnt=1;memset(a,0,sizeof(a));
int len=strlen(s+1);
for(int i=len,j=1;i;i--)
{
if(j==base)j=1,cnt++;
a[cnt]+=(s[i]-'0')*j;j*=10;
}
}
}A,B,C;
bigint operator/(bigint x,int y)
{
bigint res;res.cnt=x.cnt;
ll k=0ll;
for(int i=x.cnt;i;i--)
{
k=k*base+x.a[i];
res.a[i]=k/y;
k%=y;
}
res.clear();
return res;
}
int main()
{
scanf("%s%d",s+1,&k);
A.init2(s);
C=A/k;
C.print();
return 0;
}
高精除高精:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=110;
const int base=10;
char a[maxn],b[maxn];
struct bigint
{
ll cnt;
ll a[maxn];
bigint(){cnt=0;memset(a,0,sizeof(a));}
inline void clear(){while(!a[cnt]&&cnt>1)cnt--;}
inline void print()
{
printf("%lld",a[cnt]);
for(int i=cnt-1;i;i--)printf("%lld",a[i]);
puts("");
}
inline void init1(ll x)
{
cnt=0;memset(a,0,sizeof(a));
while(x)a[++cnt]=x%base,x/=base;
}
inline void init2(char* s)
{
cnt=1;memset(a,0,sizeof(a));
int len=strlen(s+1);
for(int i=len,j=1;i;i--)
{
if(j==base)j=1,cnt++;
a[cnt]+=(s[i]-'0')*j;j*=10;
}
}
inline void add(ll k)
{
if(!k&&cnt==1&&!a[1])return;//!!
for(int i=cnt;i;i--)a[i+1]=a[i];
a[1]=k;cnt++;
}
bool operator<(const bigint& x)const
{
if(cnt==x.cnt)
{
int i;
for(i=cnt;a[i]==x.a[i]&&i>1;i--);
if(i>=1)return a[i]<x.a[i];
else return 0;
}
else return cnt<x.cnt;
}
}A,B,C;
bigint operator-(bigint x,bigint y)
{
bigint res=x;
for(int i=1;i<=x.cnt;i++)
{
res.a[i]-=y.a[i];
if(res.a[i]<0)res.a[i+1]--,res.a[i]+=base;
}
res.clear();
return res;
}
bigint operator/(bigint x,bigint y)
{
bigint res,k;res.cnt=x.cnt;
for(int i=x.cnt;i;i--)
{
k.add(x.a[i]);
while(!(k<y))k=k-y,res.a[i]++;
}
res.clear();
return res;
}
int main()
{
scanf("%s%s",a+1,b+1);
A.init2(a),B.init2(b);
C=A/B;
C.print();
return 0;
}