题解 P1932 【A+B A-B A*B A/B A%B Problem】
更新一次~~
看到好多人卡到我前面去了，心情复杂，于是又写了一个更快一点的。现在16ms，还是第一。没有用vector，用起来的确有点麻烦。
除法的实现方法改了一下，改成每一个1e9之内二分答案，这样复杂度还是O(n^2)，但是常数小了很多。
// luogu-judger-enable-o2
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cassert>
typedef int i32;
typedef unsigned u32;
typedef unsigned long long u64;
struct BigInt
{
const static u32 exp = 9;
const static u32 mod = 1000000000;
static i32 abs_comp(const BigInt &lhs, const BigInt &rhs)
{
if (lhs.len != rhs.len)
return lhs.len < rhs.len ? -1 : 1;
for (u32 i = lhs.len - 1; ~i; --i)
if (lhs.val[i] != rhs.val[i])
return lhs.val[i] < rhs.val[i] ? -1 : 1;
return 0;
}
u32 *val, len, sgn;
BigInt(u32 *val = nullptr, u32 len = 0, u32 sgn = 0) : val(val), len(len), sgn(sgn) {}
// copy_to cannot guarantee val[x] == 0 for x >= len
// other function should set (the position they assume to be zero) as zero
void copy_to(BigInt &dst) const
{
dst.len = len, dst.sgn = sgn;
memcpy(dst.val, val, sizeof(u32) * len);
}
void trim()
{
while (len && !val[len - 1])
--len;
if (len == 0)
sgn = 0;
}
void add(BigInt &x)
{
if (sgn ^ x.sgn)
return x.sgn ^= 1, sub(x);
val[len = std::max(len, x.len)] = 0;
for (u32 i = 0; i < x.len; ++i)
if ((val[i] += x.val[i]) >= mod)
val[i] -= mod, ++val[i + 1];
for (u32 i = x.len; i < len && val[i] >= mod; ++i)
val[i] -= mod, ++val[i + 1];
if (val[len])
++len;
}
void sub(BigInt &x)
{
if (sgn ^ x.sgn)
return x.sgn ^= 1, add(x);
if (abs_comp(*this, x) < 0)
std::swap(*this, x), sgn ^= 1;
val[len] = 0;
for (u32 i = 0; i < x.len; ++i)
if ((val[i] -= x.val[i]) & 0x80000000)
val[i] += mod, --val[i + 1];
for (u32 i = x.len; i < len && val[i] & 0x80000000; ++i)
val[i] += mod, --val[i + 1];
trim();
}
void mul(BigInt &x, u32 *ext_mem)
{
assert(this != &x);
memcpy(ext_mem, val, sizeof(u32) * len);
memset(val, 0, sizeof(u32) * (len + x.len));
for (u32 i = 0; i < len; ++i)
for (u32 j = 0; j < x.len; ++j)
{
u64 tmp = (u64)ext_mem[i] * x.val[j] + val[i + j];
val[i + j] = tmp % mod;
val[i + j + 1] += tmp / mod;
}
len += x.len, sgn ^= x.sgn;
trim();
}
void mul(u32 x)
{
if (x & 0x80000000)
x = -x, sgn ^= 1;
u64 carry = 0;
for (u32 i = 0; i < len; ++i)
{
carry += (u64)val[i] * x;
val[i] = carry % mod;
carry /= mod;
}
if (carry)
val[len++] = carry;
trim();
}
void div(BigInt &x, BigInt &remainder, u32 *ext_mem)
{
assert(this != &x && this != &remainder);
copy_to(remainder), memset(val, 0, sizeof(u32) * len);
u32 shift = len - x.len;
if (shift & 0x80000000)
return void(len = sgn = 0);
while (~shift)
{
u32 l = 0, r = mod;
BigInt mul_test{ext_mem}, remainder_high{remainder.val + shift, remainder.len - shift};
while (l <= r)
{
u32 mid = (l + r) / 2;
x.copy_to(mul_test), mul_test.mul(mid);
abs_comp(mul_test, remainder_high) < 0 ? l = mid + 1 : r = mid - 1;
}
val[shift] = r;
x.copy_to(mul_test), mul_test.mul(r);
remainder_high.sub(mul_test), remainder.trim();
--shift;
}
sgn ^= x.sgn;
trim();
}
void div(u32 x)
{
if (x & 0x80000000)
x = -x, sgn ^= 1;
u64 carry = 0;
for (u32 i = len - 1; ~i; --i)
{
carry = carry * mod + val[i];
val[i] = carry / x;
carry %= x;
}
trim();
}
void read(const char *s)
{
sgn = len = 0;
i32 bound = 0, pos;
if (s[0] == '-')
sgn = bound = 1;
u64 cur = 0, pow = 1;
for (pos = strlen(s) - 1; pos + 1 >= exp + bound; pos -= exp, val[len++] = cur, cur = 0, pow = 1)
for (i32 i = pos; i + exp > pos; --i)
cur += (s[i] - '0') * pow, pow *= 10;
for (cur = 0, pow = 1; pos >= bound; --pos)
cur += (s[pos] - '0') * pow, pow *= 10;
if (cur)
val[len++] = cur;
}
void print()
{
if (len)
{
if (sgn)
putchar('-');
printf("%u", val[len - 1]);
for (u32 i = len - 2; ~i; --i)
printf("%0*u", exp, val[i]);
}
else
putchar('0');
puts("");
}
};
const int N = 1e4 + 20;
u32 a_[N], b_[N], r_[N], tmp[N * 2];
char sa[N], sb[N];
int main()
{
scanf("%s%s", sa, sb);
{
BigInt a{a_}, b{b_};
a.read(sa), b.read(sb), a.add(b), a.print();
}
{
BigInt a{a_}, b{b_};
a.read(sa), b.read(sb), a.sub(b), a.print();
}
{
BigInt a{a_}, b{b_};
a.read(sa), b.read(sb), a.mul(b, tmp), a.print();
}
{
BigInt a{a_}, b{b_}, r{r_};
a.read(sa), b.read(sb), a.div(b, r, tmp), a.print();
r.print();
}
}各位C++大佬，速度比不过python你们的心不会痛吗?
76ms，目前第一，干掉python，算是维护一下C++的尊严吧。
除法的思路是倍增，记n为输入串的长度(而非输入串代表的数值大小)，则倍增的判断次数是O(n)，每次判断只涉及到加法，复杂度也是O(n)，总体O(n^2)。二分查找的话，每次判断都是乘法，总体复杂度O(n^3)。
// luogu-judger-enable-o2
#include <bits/stdc++.h>
class BigInt
{
#define Value(x, nega) ((nega) ? -(x) : (x))
#define At(vec, index) ((index) < vec.size() ? vec[(index)] : 0)
//C风格的比较函数,其正负等于abs(lhs)-abs(rhs)的正负
static int absComp(const BigInt &lhs, const BigInt &rhs)
{
if (lhs.size() != rhs.size())
return lhs.size() < rhs.size() ? -1 : 1;
for (int i = lhs.size() - 1; i >= 0; --i)
if (lhs[i] != rhs[i])
return lhs[i] < rhs[i] ? -1 : 1;
return 0;
}
using Long = long long;
const static int Exp = 9;
const static Long Mod = 1000000000;
mutable std::vector<Long> val;
mutable bool nega = false;
//规定:0的nega必须是false,0的size必须是0
void trim() const
{
while (val.size() && val.back() == 0)
val.pop_back();
if (val.empty())
nega = false;
}
int size() const { return val.size(); }
Long &operator[](int index) const { return val[index]; }
Long &back() const { return val.back(); }
BigInt(int size, bool nega) : val(size), nega(nega) {}
BigInt(const std::vector<Long> &val, bool nega) : val(val), nega(nega) {}
public:
friend std::ostream &operator<<(std::ostream &os, const BigInt &n)
{
if (n.size())
{
if (n.nega)
putchar('-');
for (int i = n.size() - 1; i >= 0; --i)
{
if (i == n.size() - 1)
printf("%lld", n[i]);
else
printf("%0*lld", n.Exp, n[i]);
}
}
else
putchar('0');
return os;
}
friend BigInt operator+(const BigInt &lhs, const BigInt &rhs)
{
BigInt ret(lhs);
return ret += rhs;
}
friend BigInt operator-(const BigInt &lhs, const BigInt &rhs)
{
BigInt ret(lhs);
return ret -= rhs;
}
BigInt(Long x = 0)
{
if (x < 0)
x = -x, nega = true;
while (x >= Mod)
val.push_back(x % Mod), x /= Mod;
if (x)
val.push_back(x);
}
BigInt(const char *s)
{
int bound = 0, pos;
if (s[0] == '-')
nega = true, bound = 1;
Long cur = 0, pow = 1;
for (pos = strlen(s) - 1; pos >= Exp + bound - 1; pos -= Exp, val.push_back(cur), cur = 0, pow = 1)
for (int i = pos; i > pos - Exp; --i)
cur += (s[i] - '0') * pow, pow *= 10;
for (cur = 0, pow = 1; pos >= bound; --pos)
cur += (s[pos] - '0') * pow, pow *= 10;
if (cur)
val.push_back(cur);
}
BigInt &operator+=(const BigInt &rhs)
{
const int cap = std::max(size(), rhs.size()) + 1;
val.resize(cap);
int carry = 0;
for (int i = 0; i < cap - 1; ++i)
{
val[i] = Value(val[i], nega) + Value(At(rhs, i), rhs.nega) + carry, carry = 0;
if (val[i] >= Mod)
val[i] -= Mod, carry = 1; //至多只需要减一次，不需要取模
else if (val[i] < 0)
val[i] += Mod, carry = -1; //同理
}
if ((val.back() = carry) == -1) //assert(val.back() == 1 or 0 or -1)
{
nega = true, val.pop_back();
bool tailZero = true;
for (int i = 0; i < cap - 1; ++i)
{
if (tailZero && val[i])
val[i] = Mod - val[i], tailZero = false;
else
val[i] = Mod - 1 - val[i];
}
}
trim();
return *this;
}
friend BigInt operator-(const BigInt &rhs)
{
BigInt ret(rhs);
ret.nega ^= 1;
return ret;
}
BigInt &operator-=(const BigInt &rhs)
{
rhs.nega ^= 1;
*this += rhs;
rhs.nega ^= 1;
return *this;
}
//高精*高精没办法原地操作，所以实现operator*
//高精*低精可以原地操作，所以operator*=
friend BigInt operator*(const BigInt &lhs, const BigInt &rhs)
{
const int cap = lhs.size() + rhs.size() + 1;
BigInt ret(cap, lhs.nega ^ rhs.nega);
//j < l.size(),i - j < rhs.size() => i - rhs.size() + 1 <= j
for (int i = 0; i < cap - 1; ++i) // assert(0 <= ret[cap-1] < Mod)
for (int j = std::max(i - rhs.size() + 1, 0), up = std::min(i + 1, lhs.size()); j < up; ++j)
{
ret[i] += lhs[j] * rhs[i - j];
ret[i + 1] += ret[i] / Mod, ret[i] %= Mod;
}
ret.trim();
return ret;
}
BigInt &operator*=(const BigInt &rhs) { return *this = *this * rhs; }
friend BigInt operator/(const BigInt &lhs, const BigInt &rhs)
{
static std::vector<BigInt> powTwo{BigInt(1)};
static std::vector<BigInt> estimate;
estimate.clear();
if (absComp(lhs, rhs) < 0)
return BigInt();
BigInt cur = rhs;
int cmp;
while ((cmp = absComp(cur, lhs)) <= 0)
{
estimate.push_back(cur), cur += cur;
if (estimate.size() >= powTwo.size())
powTwo.push_back(powTwo.back() + powTwo.back());
}
if (cmp == 0)
return BigInt(powTwo.back().val, lhs.nega ^ rhs.nega);
BigInt ret = powTwo[estimate.size() - 1];
cur = estimate[estimate.size() - 1];
for (int i = estimate.size() - 1; i >= 0 && cmp != 0; --i)
if ((cmp = absComp(cur + estimate[i], lhs)) <= 0)
cur += estimate[i], ret += powTwo[i];
ret.nega = lhs.nega ^ rhs.nega;
return ret;
}
bool operator==(const BigInt &rhs) const
{
return nega == rhs.nega && val == rhs.val;
}
bool operator!=(const BigInt &rhs) const { return nega != rhs.nega || val != rhs.val; }
bool operator>=(const BigInt &rhs) const { return !(*this < rhs); }
bool operator>(const BigInt &rhs) const { return !(*this <= rhs); }
bool operator<=(const BigInt &rhs) const
{
if (nega && !rhs.nega)
return true;
if (!nega && rhs.nega)
return false;
int cmp = absComp(*this, rhs);
return nega ? cmp >= 0 : cmp <= 0;
}
bool operator<(const BigInt &rhs) const
{
if (nega && !rhs.nega)
return true;
if (!nega && rhs.nega)
return false;
return (absComp(*this, rhs) < 0) ^ nega;
}
void swap(const BigInt &rhs) const
{
std::swap(val, rhs.val);
std::swap(nega, rhs.nega);
}
};
const int N = 1e4 + 10;
char a[N], b[N];
int main()
{
scanf("%s%s", a, b);
BigInt ba(a), bb(b);
std::cout << ba + bb << '\n';
std::cout << ba - bb << '\n';
std::cout << ba * bb << '\n';
BigInt d;
std::cout << (d = ba / bb) << '\n';
std::cout << ba - d * bb << '\n';
return 0;
}