[TIOJ] 1006. 大數除法

題目連結:http://tioj.infor.org/problems/1006

---

基本大數，在這裡我用string做了個簡單的大數，實際上真的要用時，可能還是會採用int array之類的來壓縮空間，且也比較快

#include <iostream>
#include <string>

using namespace std;

namespace BigInt{
	//every number must be positive
	using namespace std;
	inline int c2i(char n){
		return n-'0';
	}
	inline string i2s(int n){
		return to_string(n);
	}
	inline string n0(int n){
		string k="";
		while(n--){
			k+="0";
		}
		return k;
	}
	inline string c2s(char n){
		return string(1,n);
	}
	inline string r0(string a){
		string n="";
		bool flag=false;
		for(unsigned int i=0;i<a.size();i++){
			if(a[i]!='0'&&!flag)
				flag=true;
			if(flag)
				n+=c2s(a[i]);
		}
		if(n=="")
			n="0";
		return n;
	}
	inline int cSize(string a,string b){
		string n=r0(a),m=r0(b);
		if(n==m){
			return 0;
		}
		if(n.size()>m.size()){
			return 1;
		}else if(n.size()<m.size()){
			return -1;
		}else{
			for(unsigned int i=0;i<n.size();i++){
				if(c2i(n[i])>c2i(m[i]))
					return 1;
				if(c2i(n[i])<c2i(m[i]))
					return -1;
			}
		}
		return -1;
	}
	string plus(string a,string b){
		string r="";
		int l=0;
		while(a.size()>b.size()){
			b="0"+b;
		}
		while(a.size()<b.size()){
			a="0"+a;
		}
		for(int i=a.size()-1;i>=0;i--){
			r=i2s((c2i(a[i])+c2i(b[i])+l)%10)+r;
			l=(c2i(a[i])+c2i(b[i])+l)/10;
		}
		if(l!=0)
			r=i2s(l)+r;
		return r0(r);
	}
	string minus(string a,string b){
		//a must greater than b;
		string r="";
		int l=0;
		while(a.size()>b.size()){
			b="0"+b;
		}
		for(int i=a.size()-1;i>=0;i--){
			if((c2i(a[i])-l)<c2i(b[i])){
				r=i2s((c2i(a[i])-l+10)-c2i(b[i]))+r;
				l=1;
			}else{
				r=i2s((c2i(a[i])-l)-c2i(b[i]))+r;
				l=0;
			}
		}
		return r;
	}
	string times(string a,string b){
		string r="0",k[9999];
		if(b.size() == 1){
			int l=0;
			string m="";
			for(int i=a.size()-1;i>=0;i--){
				m=i2s((c2i(a[i])*c2i(b[0])+l)%10)+m;
				l=(c2i(a[i])*c2i(b[0])+l)/10;
			}
			m=i2s(l)+m;
			return r0(m);
		}
		for(int i=b.size()-1;i>=0;i--){
			k[(b.size()-1)-i] = times(a,c2s(b[i]))+n0((b.size()-1)-i);
		}
		for(int i=b.size()-1;i>=0;i--){
			r = plus(r,k[i]);
		}
		return r0(r);
	}
	string divide(string a, string b){
		//a must greater than b
		string c="",p="";
		for(unsigned int i = 0;i<a.size();i++){
			c+=a[i];
			if(cSize(c,b)>=0){
				for(int j = 1;j<=10;j++){
					if(cSize(c,times(b,i2s(j)))<0){
						p+=i2s(j-1);
						c = minus(c,times(b,i2s(j-1)));
						j=999;

					}
				}
			}else{
				p+="0";
			}
		}
		return r0(p);
	}
}

int main(){
	string n, m;
	cin>>n;
	cin>>m;
	cout<<BigInt::divide(n,m);
	return 0;
}