比赛 防止浮躁的小练习v0.4 评测结果 AAAAAA
题目名称 增强的减法问题 最终得分 100
用户昵称 sxysxy 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2016-10-13 14:51:00
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <list>
#include <map>
#include <cstring>
#include <string>
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

class Bignum
{
	void mknum(const char *s, int len = -1)
	{
		if(*s == '-')
		{
			sign = 1;
			mknum(s+1);
			return;
		}
		int l;
		if(len == -1)
			l = strlen(s);
		else
			l = len;
		l = strlen(s);
		bits.clear();
		bits.resize(l);
		for(int i = l-1; i >= 0; i--)
			bits[l-i-1] = s[i] - '0';
		maintain();
	}
	void mknum(string &s)
	{
		mknum(s.c_str(), s.length());
	}
//	-------------
	void us_addto(Bignum &b)  // unsigned add to
	{
		int mlen = max(b.bits.size(), bits.size());
		int slen = bits.size();
		int olen = b.bits.size();
		bits.resize(mlen);
		for(int i = 0; i < mlen; i++)
		{
			int s = 0;
			if(i < slen)s += bits[i];
			if(i < olen)s += b.bits[i];
			bits[i] = s;
		}
		maintain();
	}
	class FFTer
	{
		class Complex
		{
		public:
			double real, image;
			Complex(double a = 0, double b = 0)
			{
				real = a;
				image = b;
			}
			Complex operator + (const Complex &o){return Complex(real+o.real, image+o.image);}
			Complex operator - (const Complex &o){return Complex(real-o.real, image-o.image);}
			Complex operator * (const Complex &o){return Complex(real*o.real-image*o.image, real*o.image+o.real*image);}
			Complex operator * (double k){return Complex(real*k, image*k);}
			Complex operator / (double k){return Complex(real/k, image/k);}
		};
		public:
		vector<Complex> a;  //绯绘暟鍚戦噺
		int n;				//澶氶」寮忔?鏁颁笂鐣
		FFTer(vector<int> &vec)
		{
			a.resize(vec.size());
			for(int i = 0; i < vec.size(); i++)
				a[i].real = vec[i];
			n = vec.size();
		}
		void transform()
		{
			int j = 0;
			int k;
			for(int i = 0; i < n; i++)
			{
				if(j > i)swap(a[i], a[j]);
				k = n;
				while(j & (k >>= 1))j &= ~k;
				j |= k;
			}
		}
		void FFT(bool IDFT = false)
		{
			const double Pi = IDFT?-acos(-1):acos(-1);
							//IDFT涓嶥FT閫夋嫨鏂瑰悜鐩稿弽锛堢?鍙风浉鍙嶏級
			transform();    //浜ゆ崲鍏冪礌锛堢炕杞?簩杩涘埗浣嶏紝鍏蜂綋鐪嬩笅闈㈡敞閲婏紝鍐嶅叿浣撶湅绠楀?
			for(int s = 1; s < n; s <<= 1)
			{	//绠楁硶瀵艰?涓婃槸fot s = 1 to lgn,鑰冭檻鍒扮簿搴﹂棶棰樻敼涓轰笂闈㈤偅涓?..
				for(int t = 0; t < n; t += s<<1)
				{
				//鍚堝苟[t, t+s-1]涓 [t+s, t+2*s-1] (绠楀?涓婁互鎸囨暟褰㈠紡缁欏嚭锛屾敞鎰忓埌浠栫殑s....)
				//鍚堝苟涓篬t, t+2*s-1] (鐪嬭捣鏉ュ儚鏄?簾璇? (鏈夌ず渚嬪浘鍦ㄧ畻瀵间笂锛岀敾寰楀緢褰㈣薄鐨?
				/*				涓€涓?洿绠€鍗曠殑绀轰緥鍥
					(缈昏浆杩囩▼)		  缈昏浆             鍚堝苟
					00	->	00		0-|--|---------------------------
					                  |  |          		  
					01	->	10		1-|--|---\ /---------------------
									  |	 |    X             
					10	->	01		2-|--|---/ \---------------------
									  |  |          
					11	->	11		3-|--|---------------------------
				*/
					double x = Pi/s;
					Complex omgn(cos(x), sin(x));
					Complex omg(1.0, 0.0);    //鍗曚綅鍚戦噺
					for(int m = 0; m < s; m++)
					{			//鏃嬭浆
						int a1 = m+t;
						int a2 = m+t+s;   //鍙栦袱杈圭郴鏁板悜閲忕殑绯绘暟
						//绠楀?涓婄?杩欎釜鍙?叕鍏卞瓙琛ㄨ揪寮忔秷闄
							//(鍏跺疄灏辨槸涓€涓?彉閲忚?绠椾竴娆$劧鍚庝繚瀛樹笅鏉ョ敤澶氭?...鍡?畻瀵兼€绘槸杩欎箞鏈夐€兼牸)
						Complex comm = omg * a[a2];
						a[a2] = a[a1] - comm;
						a[a1] = a[a1] + comm;  //杩欎袱涓?『搴忎笉瑕佸弽浜
						omg = omg * omgn;
					}
				}
			}
			if(IDFT)
				for(int i = 0; i < n; i++)
					a[i] = a[i] / n;
		}
		void mul(FFTer &o)
		{
			int s = 1;
			while(s < n + o.n)s <<= 1;
			n = o.n = s;
			a.resize(s);
			o.a.resize(s);
			
			FFT(false);
			o.FFT(false);
			for(int i = 0; i < n; i++)
				a[i] = a[i] * o.a[i];
			FFT(true);
		}
	};
	void us_multo(Bignum &b)
	{
		FFTer x(bits);
		FFTer y(b.bits);
		x.mul(y);
		bits.clear();
		bits.resize(x.a.size());
		for(int i = 0; i < x.n; i++)
			bits[i] = (int)(x.a[i].real+0.5);
		maintain();
	}
	void us_subto(Bignum &b) // abs(self) >= abs(other)
	{
		int mlen = length();
		int olen = b.length();
		for(int i = 0; i < mlen; i++)
		{
			int s = bits[i];
			if(i < olen)s -= b.bits[i];
			bits[i] = s;
			if(bits[i] < 0)
			{
				bits[i] += 10;
				bits[i+1] -= 1;
			}
		}
		for(int i = bits.size() - 1; !bits[i] && i >= 1; i--)bits.pop_back();
		if(bits.size() == 1 && bits[0] == 0)sign = 0;
	}
public:
	int sign;
	vector<int> bits;
	int length()
	{
		return bits.size();
	}
	void maintain()
	{
		for(int i = 0; i < bits.size(); i++)
		{
			if(i + 1 < bits.size())
				bits[i+1] += bits[i]/10;
			else if(bits[i] > 9)
				bits.push_back(bits[i]/10);
			bits[i] %= 10;
		}
		if(bits.size() == 0)
		{
			bits.push_back(0);
			sign = 0;
		}
		for(int i = bits.size() - 1; !bits[i] && i >= 1; i--)bits.pop_back();
	}
	
	Bignum(string &s)
	{
		Bignum();
		mknum(s);
	}
	Bignum(const char *s)
	{
		Bignum();
		mknum(s);
	}
	Bignum()
	{
		sign = 0;
		bits.clear();
	}
	Bignum(const Bignum& b) 
	{
		sign = b.sign;
		bits = b.bits;
	}
	
// ------------------------------------------
	bool us_cmp(Bignum &b)   //鏃犵?鍙风殑姣旇緝
	{
		if(length() != b.length())return false;
		int l = length();
		for(int i = 0; i < l; i++)
			if(bits[i] != b.bits[i])
				return false;
		return true;
	}
	bool us_larger(Bignum &b)
	{
		if(length() > b.length())return true;
		else if(length() < b.length())return false;
		int l = length();
		for(int i = l-1; i >= 0; i--)
			if(bits[i] > b.bits[i])
				return true;
		return false;
	}
	bool operator== (Bignum &o)
	{
		if(sign != o.sign)
			return false;
		return us_cmp(o);
	}
	bool operator> (Bignum &o)
	{
		if(sign == 0 && o.sign == 1)return true;
		if(sign == 1 && o.sign == 0)return false;
		if(sign == o.sign && sign)return !us_larger(o);
		return us_larger(o);
	}
	bool operator< (Bignum &o)
	{
		return !(*this == o && *this > o);   //灏忎簬灏辨槸涓嶇瓑浜庝篃涓嶅ぇ浜 
	}
	bool operator<= (Bignum &o)
	{
		return *this < o || *this == o;
	}
	bool operator>= (Bignum &o)
	{
		return *this > o || *this == o;
	}
	
// -------------------------------
	Bignum& operator+= (Bignum &o)
	{
		if(!sign && !o.sign)
		{
			us_addto(o);
			sign = 0;
		}
		else if(sign && o.sign)
		{
			us_addto(o);
			sign = 1;
		}
		else if(sign && !o.sign)
		{
			if(o.us_larger(*this))
			{
				Bignum t(o);
				t.us_subto(*this);
				*this = t;
				sign = 0;
			}else
			{
				us_subto(o);
				sign = 1;
				if(bits.size() == 1 && bits[0] == 0)sign = 0;
			}
		}else if(!sign && o.sign)
		{
			if(us_larger(o))
			{
				us_subto(o);
				sign = 0;
			}else
			{
				Bignum t(o);
				t.us_subto(*this);
				*this = t;
				sign = 1;
				if(bits.size() == 1 && bits[0] == 0)sign = 0;
			}
		}
		return *this;
	}
	Bignum operator+ (Bignum &o)
	{
		Bignum t(*this);
		t += o;
		return t;
	}

// ------------------------------
	Bignum& operator*= (Bignum &o)
	{
		us_multo(o);
		if(sign == o.sign)sign = 0;
		else sign = 1;
		return *this;
	}
	Bignum operator* (Bignum &o)
	{
		Bignum t(*this);
		t *= o;
		return t;
	}
// -------------------------------
	Bignum& operator-= (Bignum &o)
	{
		if(!sign && !o.sign) 
		{
			if(us_larger(o))
			{
				us_subto(o);
				sign = 0;
			}
			else
			{
				Bignum t(o);
				t.us_subto(*this);
				*this = t;
				sign = 1;
				if(bits.size() == 1 && bits[0] == 0)sign = 0;
			}
		}
		return *this;
	}
	Bignum operator- (Bignum &o)
	{
		Bignum t(*this);
		t -= o;
		return t;
	}
// ---------------------------------
	Bignum abs()
	{
		Bignum t(*this);
		t.sign = 0;
		return t;
	}
	
	friend istream& operator>>(istream &is, Bignum &b)
	{
		string s;
		is >> s;
		b.mknum(s);
		return is;
	}
	friend ostream& operator<<(ostream &os, Bignum b)
	{
		if(b.sign)os << '-';
		for(int i = b.bits.size()-1; i >= 0; i--)os << b.bits[i];
		return os;
	}
};

int main()
{
	freopen("sub.in", "r", stdin);
	freopen("sub.out", "w", stdout);
	Bignum a, b;
	cin >> a >> b;
	cout << a - b;
	return 0;
}