比赛 |
防止浮躁的小练习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;
}