题解 | #N的阶乘#

#include<iostream>
#include<string>
#include<map> 

using namespace std;

string sum(string a,string b){
	string::reverse_iterator it1 = a.rbegin();
	string::reverse_iterator it2 = b.rbegin();
	int carry = 0;
	string ans = "";
	while(it1!=a.rend()||it2!=b.rend()){
		int pa,pb;
		if(it1==a.rend()){
			pa=0;
		} else {
			pa=*it1-'0';
            it1++;
		}
		if(it2==b.rend()){
			pb=0;	
		} else {
			pb=*it2-'0';
            it2++;
		}
		int sum = pa+pb+carry;
		carry = sum/10;
		char digit = '0'+sum%10;
		ans = digit+ans;
	}
	if(carry!=0) ans = '1' + ans;
	return ans;
}

//使用打表法优化乘法计算
string mul(string a,string b){
	//提前打表，把0*b到9*b的结果算出来 
	map<char,string> multi;
	string generator = "0";
	multi['0'] = "0";
	for(int i=1;i<=9;i++){
		multi['0'+i] = sum(generator,b);
		generator = multi['0'+i];
	}
	//开始模拟乘法器 
	string::reverse_iterator it1 = a.rbegin();
	string ans = "0";
	int i=0;
	while(it1!=a.rend()){
		string temp = multi[*it1];
		//如果数字很大的话，先对齐再加太浪费时间了
		//不用管的部分，直接拼接字符串就行 
		int sub = ans.size()-i;
		string lower = ans.substr(sub);
		string upper = ans.substr(0,sub);
		upper = sum(upper,temp);
		ans = upper+lower;
		i++;
		it1++;
	}
	return ans;
} 

void Example6_14(){//例题6.14  清华大学  n的阶乘
	string n;
	while(cin>>n){
		string factor = "1";
		string ans = "1";
		while(factor!=n){
			factor = sum(factor,"1");
			ans = mul(ans,factor);
		}
		cout<<ans<<endl;
		
	} 
	
} 
int main(){
	Example6_14();
	return 0;
}