| 记录编号 |
274861 |
评测结果 |
AAAAAA |
| 题目名称 |
增强的减法问题 |
最终得分 |
100 |
| 用户昵称 |
 sxysxy |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.000 s |
| 提交时间 |
2016-06-29 23:41:28 |
内存使用 |
0.00 MiB |
显示代码纯文本
#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与DFT选择方向相反（符号相反）
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;
}