#18225: 給延平同仁c++AC


089487 (089487)

學校 : 國立臺灣師範大學附屬高級中學
編號 : 82069
來源 : [140.112.150.137]
最後登入時間 :
2024-10-03 16:28:37
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;
}
 
ZeroJudge Forum