a021.
大數運算
| From: [223.140.228.113] |
發表日期
:
2019-06-29 07:04
#include<bits/stdc++.h>
using namespace std;
string sum(string,string);
string min (string,string);
string multiply(string,string);
string exclusion(string,string);
bool cmp(string ,string);
int main()
{
ios::sync_with_stdio(false);
string a,b,s;
char c;
//int line=0;
while(cin>>a>>c>>b)
{
if(c=='+') s=sum(a,b);
else if(c=='-') s=min(a,b);
else if(c=='*') s=multiply(a,b);
else s=exclusion(a,b);
cout<<s<<endl;
}
}
string sum(string a,string b)
{
string k;
if(b.length()>a.length()) swap(a,b);
char c[a.length()],d[a.length()],s[a.length()];
for(int i=0;i<a.length();i++)
{
c[i]=a[i];
if(a.length()-i>b.length()) d[i]='0';
else d[i]=b[b.length()+i-a.length()];
}
int n=0,r=0,z=0;
for(int i=a.length()-1;i>=0;i--)
{
n=c[i]-'0'+d[i]-'0'+r;
if(n>=10) n=n-10,r=1;
else r=0;
s[i]=n+'0';
}
if(r==1) k+='1';
for(int i=0;i<a.length();i++) k+=s[i];
return k;
}
string min(string a,string b)
{
string k;
int m;
bool f=cmp(a,b);
if(f==false) swap(a,b);
m=(a.length()>b.length())?a.length():b.length();
char c[m],d[m];
string s;
for(int i=0;i<a.length();i++)
{
if(m-i>a.length()) c[i]='0';
else c[i]=a[a.length()+i-m];
if(m-i>b.length() )d[i]='0';
else d[i]=b[b.length()+i-m];
}
int n=0,r=0,z=0;
for(int i=a.length()-1;i>=0;i--)
{
n=c[i]-d[i]+r;
if(n>=10) n=n-10,r=1;
else if(n<0) n+=10,r=-1;
else r=0;
s+=n+'0';
}
if(r==1) k+='1';
if(f==false) k+='-';
int x=0;
bool f2=false;
for(int i=s.length()-1;i>=0;i--)
{
if(f2||s[i]!='0') f2=true,k+=s[i];
}
return k;
}
bool cmp(string a,string b)
{
if(a.length()!=b.length()) return a.length()>b.length();
for(int i=0;i<a.length();i++)
{
if(a[i]!=b[i]) return a[i]>b[i];
}
return true;
}
string exclusion(string a,string b)
{
if(!cmp(a,b)) return "0";
string c;
string k;
int z;
while(cmp(a,b))
{
k.clear();
if((a[0]-'0')/(b[0]-'0')!=0)
{
k+=(a[0]-'0')/(b[0]-'0')+'0';
for(int i=0;i<a.length()-b.length();i++) k+='0';
z=0;
while(!cmp(a,multiply(b,k)))
{
k[z]--;
if(k[z]=='0') z++,k[z]='9';
}
c=sum(c,k);
a=min(a,multiply(b,k));
}
else
{
int r=0,num=0;
num=a[0]-'0';
while(num/(b[0]-'0')<=0) r++,num=num*10+(a[r]-'0');
k=num/(b[0]-'0')+'0';
for(int i=0;i<a.length()-b.length()-r;i++) k+='0';
a=min(a,multiply(b,k));
c=sum(c,k);
}
}
bool f=false;
string s;
for(int i=0;i<c.length();i++) if(c[i]!='0'||f) f=true ,s+=c[i];
return s;
}
string multiply(string a,string b)
{
int n[(a.length()+1)+(b.length()+1)]={0};
int l=(a.length()+1)+(b.length()+1);
int c[a.length()];
int d[b.length()];
for(int i=0;i<a.length();i++) c[i]=a[i]-'0';
for(int i=0;i<b.length();i++) d[i]=b[i]-'0';
for(int i=a.length()-1;i>=0;i--)//222 * 111
{
for(int j=b.length()-1;j>=0;j--)
{
int num=c[i]*d[j];
int digit=(a.length()-i-1)+(b.length()-j-1);
n[l-digit-1]+=num%10;
n[l-digit-2]+=num/10;
if(n[l-digit-1]>=10) n[l-digit-1]-=10,n[l-digit-2]++;
}
}
for(int i=l-1;i>=0;i--) if(n[i]>10) n[i]/=10,n[i-1]+=n[i]%10;
bool f2=false;
string k;
for(int i=0;i<l;i++)
{
if(n[i]!=0||f2) k+=(n[i]+'0'),f2=true;
}
return k;
}