大整数类型
Morning_Glory
2018-10-14 12:56:41
### 下面是本人自己做的一个大整数类型，需要的可以拿走用，可以节约很多时间，用的时候注意没有负数，想要练习重载运算符也可以看一下，有不好的地方欢迎指出
```cpp
#include <bits/stdc++.h>
using namespace std;
//该Int 类型只能 ++i，不能i++
//不支持负数运算
struct Int{
int num[101];
bool fs;//是否是负数，不过现在还不支持负数运算
Int(){fs=false;memset(num,0,sizeof(num));}//初始化负数为非负数,数字为0
void re (){reverse(num+1,num+num[0]+1);}//翻转
void add (int k){num[++num[0]]=k;}//就是 a*10+k ，用于除法
Int & operator = (Int x){
//重载赋值号 同类型赋值将所有状态赋过来即可
memset(num,0,sizeof(num));
for (int i=0;i<=x.num[0];i++) num[i]=x.num[i];
//将改变后的值返回，可以连续赋值
return *this;
}
Int operator = (long long x){
//先将x转为该类型，再原样赋值
int i=1;
memset(num,0,sizeof(num));
while (x) num[++num[0]]=x%10,x/=10;
reverse(num+1,num+num[0]+1);
return *this;
}
bool operator == (Int x){
//重载==号
if (fs^x.fs||num[0]!=x.num[0]) return false;//符号不同或长度不同即可返回不同
for (int i=1;i<=num[0];i++) if (num[i]!=x.num[i]) return false;//一个一个去比较
return true;
}
bool operator < (const Int x){
if (num[0]<x.num[0]) return true;
if (num[0]>x.num[0]) return false;
for (int i=num[0];i>=1;i--)
if (num[i]!=x.num[i]) return num[i]<x.num[i];
return false;//默认>
}
bool operator < (long long x){
long long y=x,len=0;
while (y) ++len,y/=10;//看看该低精数的位数
if (num[0]==1&&num[1]==0||!num[0])//如果自己是0
if (x) return true;//x不是0
else return false;
if (len==num[0])//如果他们位数相同，就说明这个高精数其实是一个低精数
for (int i=num[0];i>=1;--i) y=(y<<3)+(y<<1)+num[i];
else return num[0]<len;
return y<x;
}
bool operator <= (Int x){
//重载<=号
if (num[0]<x.num[0]) return true;
if (num[0]>x.num[0]) return false;
for (int i=num[0];i>=1;i--)
if (num[i]!=x.num[i]) return num[i]<x.num[i];
return true;
//默认是<=的
}
bool operator <= (long long x){
long long y=x,len=0;
while (y) ++len,y/=10;
if (num[0]==1&&num[1]==0||!num[0])
if (x) return true;
if (len==num[0])
for (int i=num[0];i>=1;--i) y=(y<<3)+(y<<1)+num[i];
else return num[0]<=len;
return y<=x;
}
bool operator > (Int x){
//在已经重载了<=号时，便可以直接调用了
return !(*this<=x);
}
bool operator > (long long x){
return !(*this<=x);
}
inline bool operator >= (Int x){
return !(*this<x);
}
inline bool operator >= (long long x){
return !(*this<x);
}
Int operator * (Int x){
//重载*号
//下面是正常高精模板
Int y;
y.num[0]=num[0]+x.num[0];
for (int i=1;i<=num[0];i++)
for (int j=1;j<=x.num[0];j++){
y.num[i+j-1]+=num[i]*x.num[j];
y.num[i+j]+=y.num[i+j-1]/10;
y.num[i+j-1]%=10;
}
while (y.num[0]>1&&!y.num[y.num[0]]) --y.num[0];//留一个长度表示0
return y;
}
Int operator * (long long x){
//同样现将x转化，再调用已重载过的运算符
Int y;
while (x){
y.num[++y.num[0]]=x%10;
x/=10;
}
return *this*y;
}
Int operator + (Int x){
//重载+号，下面是正常高精加
Int y;
y.num[0]=max(num[0],x.num[0])+1;
for (int i=1;i<=y.num[0];i++){
y.num[i]+=x.num[i]+num[i];
y.num[i+1]=y.num[i]/10;
y.num[i]%=10;
}
while (y.num[0]>1&&!y.num[y.num[0]]) --y.num[0];
return y;
}
Int operator + (long long x){
//同理
Int y;
while (x){
y.num[++y.num[0]]=x%10;
x/=10;
}
return (y+*this);
}
//下面同样的
Int operator += (Int x){
*this=*this+x;
return *this;
}
Int operator += (long long x){
*this=*this+x;
return *this;
}
Int operator ++ (){
*this=*this+1;
return *this;
}
Int operator *= (Int x){
*this=*this*x;
return *this;
}
Int operator *= (long long x){
*this=*this*x;
return *this;
}
Int operator - (Int x){
//重载-号，下面是正常模板
Int y;
int t;
y.num[0]=num[0];
for (int i=1;i<=num[0];i++){
y.num[i]+=num[i]-x.num[i];
if (y.num[i]<0){
y.num[i]+=10;
y.num[i+1]--;
}
}
while (y.num[0]>1&&!y.num[y.num[0]]) y.num[0]--;
return y;
}
Int operator -= (Int x){
*this=*this-x;
return *this;
}
Int operator / (Int x){
//重载除号
Int y,tans;//tans 记录答案
for (int i=num[0];i>=1;--i){
y.add(num[i]);//这里就是先从大的除，稍微理解一下就可以了
y.re();
while (y.num[0]&&!y.num[y.num[0]]) --y.num[0];
while (y>=x&&y>0) y-=x,++tans.num[i];
y.re();
}
tans.num[0]=num[0];
while (tans.num&&!tans.num[tans.num[0]]) --tans.num[0];
return tans;
}
Int operator / (long long x){//除以低精
Int tans;
long long t=0;
for (int i=num[0];i>=1;--i){
t=(t<<3)+(t<<1)+num[i];
tans.num[i]=t/x;
if (!tans.num[0]&&tans.num[i]) tans.num[0]=i;
t%=x;
}
return tans;
}
Int operator /= (Int x){
*this=*this/x;
return *this;
}
Int operator /= (long long x){
*this=*this/x;
return *this;
}
Int operator % (Int x){
// 和除法一样输出剩下的数就好
Int y;
for (int i=num[0];i>=1;--i){
y.add(num[i]);
y.re();
while (y.num[0]&&!y.num[y.num[0]]) --y.num[0];
while (y>=x&&y>0) y-=x;
y.re();
}
return y;
}
Int operator % (long long x){
return *this-*this/x*x;
}
Int operator %= (Int x){
*this=*this%x;
return *this;
}
friend ostream & operator <<(ostream & os,Int x){
if (x.num[0]==0){os<<0;return os;}
if (x.fs) os<<'-';//是负数就先输出-号，虽然现在没什么用
for (int i=x.num[0];i;i--) os<<x.num[i];
return os;
}
friend istream & operator >>(istream & is,Int &x){
char s[10001];
is>>s+1;//输入可以先输入一个char型 再慢慢 赋值
x.num[0]=strlen(s+1);
for (int i=x.num[0];i>0;i--) x.num[i]=s[x.num[0]-i+1]-'0';
if (x.num[0]<0){x.num[0]=-x.num[0];x.fs=true;}
return is;
}
};
```
压位高精
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10001;
const int power = 4;//压多少位 达到10位把int 改为 long long
const int base = 10000;//10的几次方
//输入不是cin而是a.in()
//输出不是cout而是a.out()
//不能++
//有这些运算符可用 + += - -= * *= / /= < <= > >=
struct Int {
int num[maxn];
Int (){memset(num,0,sizeof(num));}
void add (int k){if (k||num[0]) num[++num[0]]=k;}
void re(){reverse (num+1,num+num[0]+1);}
friend bool operator < (const Int & x,const Int & y){
if (x.num[0]<y.num[0]) return true;
if (x.num[0]>y.num[0]) return false;
for (int i=x.num[0];i>=1;--i)
if (x.num[i]!=y.num[i]) return x.num[i]<y.num[i];
return false;
}
friend bool operator <= (const Int & x,const Int & y){
if (x.num[0]<y.num[0]) return true;
if (x.num[0]>y.num[0]) return false;
for (int i=x.num[0];i>=1;i--)
if (x.num[i]!=y.num[i]) return x.num[i]<y.num[i];
return true;
}
friend bool operator == (const Int & x,const Int & y){
for (int i=0;i<=x.num[0];i++) if (x.num[i]!=y.num[i]) return false;
return true;
}
friend bool operator > (const Int & x,const Int & y){
return !(x<=y);
}
friend bool operator >= (const Int & x,const Int & y){
return !(x<y);
}
void in(){
int k=base,len;
char s[maxn];
scanf("%s",s+1);
len=strlen(s+1);//从后往前读
for (int i=len;i>=1;--i,k*=10){
if (k==base) ++num[0],k=1;
num[num[0]]=num[num[0]]+k*(s[i]-'0');
}
}
void out (){
printf("%d",num[num[0]]);
for (int i=num[0]-1;i>=1;--i) printf("%0*d",power,num[i]);
printf("\n");
}
Int operator = (Int x){
memset(num,0,sizeof(num));
for (int i=0;i<=x.num[0];i++) num[i]=x.num[i];
return *this;
}
Int operator = (long long x){
memset(num,0,sizeof(num));
while (x) num[++num[0]]=x%base,x/=base;
return *this;
}
Int operator + (Int x){
Int y;
y.num[0]=max(num[0],x.num[0])+1;
for (int i=1;i<=y.num[0];i++){
y.num[i]+=num[i]+x.num[i];
y.num[i+1]+=y.num[i]/base;
y.num[i]%=base;
}
while (!y.num[y.num[0]]) --y.num[0];
return y;
}
Int operator += (Int x){
*this=*this+x;
return *this;
}
Int operator - (Int x){
Int y;
for (int i=1;i<=y.num[0];++i){
y.num[i]+=num[i]-x.num[i];
if (y.num[i]<0) y.num[i]+=base,--y.num[i+1];
}
while (y.num[0]&&!y.num[y.num[0]]) --y.num[0];
return y;
}
Int operator -= (Int x){
for (int i=1;i<=num[0];++i){
num[i]-=x.num[i];
if (num[i]<0) num[i]+=base,--num[i+1];
}
while (num[0]&&!num[num[0]]) --num[0];
return *this;
}
Int operator * (Int x){
Int y;
y.num[0]=num[0]+x.num[0];
for (int i=1;i<=num[0];++i)
for (int j=1;j<=x.num[0];++j){
y.num[i+j-1]+=num[i]*x.num[j];
y.num[i+j]+=y.num[i+j-1]/base;
y.num[i+j-1]%=base;
}
while (y.num[0]&&!y.num[y.num[0]]) --y.num[0];
return y;
}
Int operator *= (Int x){
*this=*this*x;
return *this;
}
Int operator / (Int x){
Int ans,y,z;
z.num[1]=z.num[0]=1;
for (int i=num[0];i>=1;--i){
y.add(num[i]);
y.re();
while (y.num[0]&&!y.num[y.num[0]]) --y.num[0];
while (y>=x&&y>=z) y-=x,++ans.num[i];
y.re();
}
ans.num[0]=num[0];
while (ans.num[0]&&!ans.num[ans.num[0]]) --ans.num[0];
return ans;
}
Int operator /= (Int x){
*this=*this/x;
return *this;
}
Int operator % (Int x){
Int y;
for (int i=num[0];i>=1;--i){
y.add(num[i]);
y.re();
while (y>=x) y-=x;
y.re();
}
while (y.num[0]&&!y.num[y.num[0]]) --y.num[0];
return y;
}
Int operator %= (Int x){
*this=*this%x;
return *this;
}
};
```