题解 | #Powerful Calculator#

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

void gen_vect(vector<int>& vec,int n)
{
	while(n--)
		vec.push_back(rand());
}
bool cmp_up(const int& a,const int& b)
{
	return a<b;
}
bool cmp_lower(const int& a, const int& b)
{
	return a>b;
}

void gen_set(set<int>& s, int n)
{
	while(n--)	s.insert(rand()%15);
}


typedef long long ll;


ll trav(int n){
	if(n==0)	return 1;
	else if(n<=2)	return n;
	return n*trav(n-1);
} 

void add(vector<int>& ans,const vector<int>& a,const vector<int>& b)
{
	ans.clear();
	ans.resize(a.size()+b.size());
	for(int i=0;i<ans.size();++i) ans[i]=0;
	
	int pa(a.size()-1),pb(b.size()-1);
	int p(0),n(0);
	while(pa>=0&&pb>=0){
		ans[p]+=a[pa]+b[pb];
		int kn=ans[p];
		int t(p);
		while(ans[t]>=10){
			ans[t++]%=10;
			ans[t]+=1;
		} 
	 	if(t>n) n=t;
	 	
	 	pb--;
	 	pa--;
	 	p++;
	}
	if(pa>=0)	
		while(pa>=0){
			ans[p]+=a[pa];
			int nk=ans[p];
			int t(p);
			while(ans[t]>=10){
				ans[t++]%=10;
				ans[t]+=1;
			} 
		 	if(t>n) n=t;
		
			p++; 
			pa--;
		}
	if(pb>=0)
		while(pb>=0){
			ans[p]+=b[pb];
			int nk=ans[p];
			int t(p);
			while(ans[t]>=10){
				ans[t++]%=10;
				ans[t]+=1;
			} 
		 	if(t>n) n=t;
	 	
			p++;
			pb--;
		}
	
	
	for(int i=n;i>=0;--i)	cout<<ans[i];	
	cout<<endl;
	return; 
}

/*
大数减法   123 - 234
	if a<b then 标记负，算b-a
	else 每一位 
	 if 够减 then 相减
	 else 借位 then 3-4+10 and 高位-1（while调整） 

*/

bool operator<(const vector<int>& a,const vector<int>& b){
	if(a.size()<b.size())	return true;
	else if(a.size()>b.size())	return false;
	int len=a.size();
	for(int i=0;i<len;++i){
		int t1=a[i],t2=b[i];
		if(a[i]<b[i]) return true;
		else if(a[i]>b[i]) return false;
		else continue;
	}
	return false;
}

void del(vector<int>& ans, vector<int> a,vector<int> b){
	ans.clear();
	bool flag(true);
	if(a<b){
		flag=false;
		vector<int> tp=a;
		a=b;
		b=tp;
	} 
	int pa(a.size()-1),pb(b.size()-1);
	int p(0),borrow(0);
	while(pb>=0&&pa>=0){
		int tmp= a[pa]-b[pb]-borrow;	//可能不够减 
		int z1=a[pa],z2=b[pb];
		if(tmp<0)	{ans[p]=tmp+10;borrow=1;}
		else {ans[p]=tmp; borrow=0;}
		
		//adjust
		/*int t(pa);
		while(tmp<0){
			t--;
			a[t]--;
			tmp=a[t];
		}*/
		
		pa--;
		pb--;
		p++;
	}
	while(pa>=0){
		if(borrow)	{ans[p]=a[pa]-borrow;borrow=0;}
		else	ans[p]=a[pa];
		
		p++;
		pa--;
	}
	
	if(!flag) cout<<'-';
	bool zero(false);
	for(int i=p-1;i>=0;--i){
		if(ans[i]!=0||zero) 
		{
			cout<<ans[i];
			if(!zero) zero=true;
		}
	}
	
	cout<<endl;
}

/*大数乘法
	123*123
	3*3+3*2*10*3+1*100*3
	2*...
	从a.size()-1 ~ 0 
		b.size()-1 ~ 0 每移动一位都使得base+1，即ans[i+base]=out;
	并且对ans[i]进行向上调整 while(a[i]>9)
*/
void multi(vector<int>& ans,vector<int> a,vector<int> b){
	
	//initial
	ans.clear();
	ans.resize(a.size()+b.size()+1);
	for(int i=0;i<ans.size();++i)	ans[i]=0;
	
	int p(0),n(0);
	
	int pa(a.size()-1),pb(b.size()-1);
	for(int i=pa,basA=0;i>=0;i--,basA++){
		for(int j=pb,basB=0;j>=0;j--,basB++){
			int bas=basA+basB;
			int tp = a[i]*b[j];
			ans[bas]+= tp;
			int t(bas);
			while(ans[t]>9){
				int ent=ans[t]/10;
				ans[t]%=10;
				t++;
				ans[t]+=ent;	//forward regregation 
			}
			if(t>n)	n=t;
			
			p++;			//每一轮次后增长一个数量级 
		}
	} 
	bool zero(false);
	for(int i=n;i>=0;--i){
		if(ans[i]!=0||zero) 
		{
			cout<<ans[i];
			if(!zero) zero=true;
		}
	}
	cout<<endl;
}

int main()
{	
	string a,b;
	vector<int> ans,A, B; 
	while(cin>>a>>b){
		//转换为数字
		for(int i=0;i<a.size();++i)	A.push_back(a[i]-'0');
		for(int i=0;i<b.size();++i)	B.push_back(b[i]-'0');
	 	add(ans,A,B);
	 	del(ans,A,B);
	 	multi(ans,A,B);
	 	
	 	ans.clear();
	 	A.clear();
	 	B.clear();
	}
	
 	return 0;
}