#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int min(int,int);
class INT
{
public:
// INT(int n);
INT(string);
void print(INT i);
string add(INT b);
string minus(INT b);
INT cheng(INT a);
friend int change(INT& a,INT& b);
friend int cifang(int i);
INT& operator+(INT);
INT& operator-(INT);
INT& operator*(INT);
INT& operator/ (INT &b);
//INT& operator = (INT &b);
bool operator <(INT &b);
private:
unsigned short*ptr;
int size;
bool is;
};
INT& pre (INT& a);
INT& INT::operator +(INT a)
{
return *(new INT(this->add(a)));
}
INT& INT::operator -(INT a)
{
return *(new INT(this->minus(a)));
}
INT& INT::operator *(INT a)
{
return*(new INT(this->cheng(a)));
}
/*inline INT::INT(int n)
{
if(n<0)
{
n=-n;is=true;
}
size=3;
ptr=new unsigned short[size];
ptr[0]=n%10000;
ptr[1]=n/10000%10000;
ptr[2]=n/100000000;
}*/
inline INT::INT(string str)
{
int len;
int i,j;
if(str[0]=='-')
{
is=true;
str.erase(str.begin(),str.begin()+1);
}
else is=false;
len=str.size();
size=ceil(len/4.0);
ptr=new unsigned short[size];
for(i=0;i<size;++i)
{
int x=0; int y=1;
for(j=0;j<4;j++)
{
if(len-1-i*4-j>=0)
x+=y*(str[len-1-i*4-j]-'0');
else break;
y*=10;
}
ptr[i]=x;
}
/* if(is)
{
for(i=0;i<size&&ptr[i]==0;++i);
if(i==size) is=false;
}*/
}
void INT::print(INT a)
{
int i;
if(is)
{
cout<<"-";
is=false;
}
for(i=a.size-1;i>=0;i--)
{
if(a.ptr[i]<1000&&i!=a.size-1)
{
if(a.ptr[i]<10)
cout<<"000"<<a.ptr[i];
else if(a.ptr[i]<100)
cout<<"00"<<a.ptr[i];
else
cout<<"0"<<a.ptr[i];
}
else
cout<<a.ptr[i];
}
cout<<endl;
}
string INT::add(INT b)
{
INT a=*this;
string resultstr="";
string resultstr2="";
string resultstr3="";
char str[4];
int jin=0;
int sum;
for(int k=0;k<min(a.size,b.size);k++)
{
sum=a.ptr[k]+b.ptr[k]+jin;
if(sum>10000)
{
jin=1;
sum=sum-10000;
}
else
{
jin=0;
}
str[3]=sum%10+'0';
str[2]=(sum%100-sum%10)/10+'0';
str[1]=sum%1000/100+'0';
str[0]=sum/1000+'0';
for(int i=3;i>=0;i--)
resultstr=str[i]+resultstr;
}
//判断a,b在size大小
if(a.size>b.size)
{
for(k=b.size;k<a.size;k++)
{
a.ptr[k]=a.ptr[k]+jin;
if(a.ptr[k]>10000)
{
jin=1;
a.ptr[k]-=10000;
}
else
{
jin=0;
}
str[3]=a.ptr[k]%10+'0';
str[2]=(a.ptr[k]%100-a.ptr[k]%10)/10+'0';
str[1]=a.ptr[k]%1000/100+'0';
str[0]=a.ptr[k]/1000+'0';
for(int i=3;i>=0;i--)
resultstr2=str[i]+resultstr2;
}
resultstr=resultstr2+resultstr;
if(jin==1)
resultstr="1"+resultstr;
return resultstr;
}
else if(a.size==b.size)
{
if(jin==1)
resultstr="1"+resultstr;
return resultstr;
}
else
{
for(k=a.size;k<b.size;k++)
{
b.ptr[k]=b.ptr[k]+jin;
if(b.ptr[k]>10000)
{
jin=1;
sum-=10000;
}
else
{
jin=0;
}
str[3]=b.ptr[k]%10+'0';
str[2]=(b.ptr[k]%100-b.ptr[k]%10)/10+'0';
str[1]=b.ptr[k]%1000/100+'0';
str[0]=b.ptr[k]/1000+'0';
for(int i=3;i>=0;i--)
resultstr3=str[i]+resultstr3;
}
resultstr=resultstr3+resultstr;
if(jin==1)
resultstr="1"+resultstr;
return resultstr;
}
// char* x=resultstr.assign();
return resultstr;
}
string INT::minus(INT b)
{
INT a=*this;
string resultstr="";
string resultstr2="";
string resultstr3="";
char str[4];
int jie=0;
int res;
int pos=0;
if(a.size<b.size)
{
pos=change(a,b);
}
if(a.size>b.size)
{
for(int k=0;k<min(a.size,b.size);k++)
{
res=a.ptr[k]-b.ptr[k]-jie;
if(res<0)
{
jie=1;
res=10000+res;
}
else
{
jie=0;
}
str[3]=res%10+'0';
str[2]=(res%100-res%10)/10+'0';
str[1]=res%1000/100+'0';
str[0]=res/1000+'0';
for(int i=3;i>=0;i--)
resultstr=str[i]+resultstr;
}
for(k=b.size;k<a.size;k++)
{
a.ptr[k]=a.ptr[k]-jie;
jie=0;
str[3]=a.ptr[k]%10+'0';
str[2]=(a.ptr[k]%100-a.ptr[k]%10)/10+'0';
str[1]=a.ptr[k]%1000/100+'0';
str[0]=a.ptr[k]/1000+'0';
for(int i=3;i>=0;i--)
resultstr2=str[i]+resultstr2;
}
resultstr=resultstr2+resultstr;
if(pos) resultstr="-"+resultstr;
return resultstr;
}
if(a.size==b.size)
{
if(a.ptr[a.size-1]<b.ptr[a.size-1])
{
pos=change(a,b);
}
for(int k=0;k<a.size;k++)
{
res=a.ptr[k]-b.ptr[k]-jie;
if(res<0)
{
jie=1;
res=10000+res;
}
else
{
jie=0;
}
str[3]=res%10+'0';
str[2]=(res%100-res%10)/10+'0';
str[1]=res%1000/100+'0';
str[0]=res/1000+'0';
for(int i=3;i>=0;i--)
resultstr=str[i]+resultstr;
}
if(pos) resultstr="-"+resultstr;
return resultstr;
}
}
int min(int x,int y)
{
return x<y?x:y;
}
int change(INT& a,INT& b)
{
INT temp("");
temp=a;
a=b;
b=temp;
return 1;
}
INT INT::cheng(INT a)
{
/*INT b=*this;
int m=0;
int n=0;
int sum=0;
int sum1=0;
int sum2=0;
string resultstr="";
for(int i=0;i<a.size;i++)
{
m=cifang(i);
sum=sum+a.ptr[i]*m;
}
for(int k=0;k<b.size;k++)
{
n=cifang(k);
sum1=sum1+b.ptr[k]*(n);
}
sum2=sum*sum1;
char str;
int sum3=0;
int len=0;
for(int s=sum2;s>10;s=s/10)
{
len++;
}
len=len+1;
for(i=1;i<=len;i++)
{
if(0<=sum2<10)
{str=sum2+'0';}
else
{
sum3=sum2%10;
sum2=sum2/10;
str=sum3+'0';
}
resultstr=str+resultstr;
}
return resultstr;*/
INT b=*this;
INT m("");
int sum=0;
int n=0;
for(INT i("0");i<b;pre(i))
{
m=INT(m+a);
}
return m;
}
INT & pre (INT & a)
{
INT b("1");
a=INT(a+b);
return a;
}
bool INT::operator < (INT &b)
{
INT a=*this;
if(a.size>b.size)
{
return 0;
}
if(a.size==b.size)
{
INT c(a-b);
return c.is;
}
else
{
return 1;
}
}
/*INT& INT::operator = (INT &b)
{
INT a=*this;
a.size=b.size;
for(int i=0;i<b.size;i++)
{
a.ptr[i]=b.ptr[i];
}
return a;
}*/
INT& INT::operator / (INT &b)
{
INT a=*this;
INT n("1");
for(INT i("0");i<a;pre(i))
{
if((i*b)<a)
{
}
else
{
return i=i-n;
}
}
}
int main()
{
INT a("10000");
INT b("999999999999999999");
a.print(a);
b.print(b);
INT c("");
c=a*b;
c.print(c);
return 0;
}
//主要优化乘法的算法
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
