提交记录 20256


用户 题目 状态 得分 用时 内存 语言 代码长度
RBTree 1005a. 【模板题】高精度除法 Accepted 100 2.527 ms 744 KB C++17 12.06 KB
提交时间 评测时间
2023-10-03 20:22:52 2023-10-03 20:22:54
// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// This is my kingdom code.

// #define EFILE ""
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define _CONSOLE 0
#define _MULTI_TESTS 0

using namespace std;
using tp = long long;
constexpr tp ZERO = 0, ONE = 1, INF32 = -1u >> 2, INF = -1ull >> 2;

// :\

namespace BigInteger {
const double PI = acos(-1), PI2 = 2 * PI;

struct complex {
  double x, y;
  
  complex() = default;
  complex(double _x, double _y) : x(_x), y(_y) {}

  complex operator+(const complex &a) const { return complex(x + a.x, y + a.y); }
  complex operator-(const complex &a) const { return complex(x - a.x, y - a.y); }
  complex operator*(const complex &a) const { return complex(x *a.x - y *a.y, x *a.y + y *a.x); }
  complex operator*(const double a) const { return complex(x * a, y * a); }
};

vector<complex> omega;

size_t limit(size_t n) {
  size_t cnt = 0;
  for (size_t i = 1; i < n; i <<= 1) ++cnt;
  return cnt;
}

void butterfly(vector<complex>& a, size_t os, size_t m, size_t k) {
  for (size_t i = 0; i < m; ++i) {
    complex &x = a[i + os], &y = a[i + m + os], tmp = y * omega[i + k];
    y = x - tmp;
    x = x + tmp;
  }
}

void FFT(vector<complex>& a, size_t lim, char I) {
  const size_t n = 1ull << lim, size = 1ull << (lim < 16 ? lim : 16);
  for (size_t i = 0, j = 0; i < n; ++i) {
    size_t l = n / 2;
    if (i < j) swap(a[i], a[j]);
    while ((j ^= l) < l) l /= 2;
  }
  for (size_t i = 0; i < n; i += size) {
    for (size_t m = 1, k = 2; m < size; m *= 2, k *= 2) {
      for (size_t j = 0; j < size; j += k) butterfly(a, i + j, m, k);
    }
  }
  for (size_t m = size, k = size << 1; m < n; m <<= 1, k <<= 1) {
    for (size_t j = 0; j < n; j += k) butterfly(a, j, m, k);
  }
  if (I == -1) {
    for (size_t i = 1, e = n / 2; i <= e; ++i) swap(a[i], a[n - i]);
    for (size_t i = 0; i < n; ++i) a[i] = a[i] * (1. / n);
  }
}

void FFT(vector<complex>& a, vector<complex>& b, size_t lim, char I) {
  size_t n = 1ull << lim;
  vector<complex> p(n + 1);
  if (I != -1) {
    for (size_t i = 0; i < n; ++i) p[i] = complex(a[i].x, b[i].x);
    FFT(p, lim, 1);
    p[n] = p[0];
    for (size_t i = 0; i < n; ++i) {
      const double x = p[i].x, y = p[i].y, z = p[n - i].x, w = -p[n - i].y;
      a[i] = complex((x + z) * .5, (y + w) * .5);
      b[i] = complex((y - w) * .5, (z - x) * .5);
    }
  } else {
    for (size_t i = 0; i < n; ++i) p[i] = complex(a[i].x - b[i].y, a[i].y + b[i].x);
    FFT(p, lim, -1);
    for (size_t i = 0; i < n; ++i) a[i].x = p[i].x, a[i].y = p[i].y;
  }
}

#define DIGIT 4
#define M 10000

struct BigInt {
  size_t n;
  vector<long long> a;

  BigInt() : a(2), n(1) {}
  BigInt(unsigned long long x) : a(3) { a[1] = x % M; a[2] = x / M; n = 1 + !!a[2]; }
};

char cmp(const BigInt &a, const BigInt &b) {
  if (a.n != b.n) return a.n < b.n ? -1 : 1;
  for (size_t i = a.n; i >= 1; --i) {
    if (a.a[i] != b.a[i]) return a.a[i] < b.a[i] ? -1 : 1;
  }
  return 0;
}

void add(BigInt &ans, const BigInt &a, const BigInt &b) {
  ans.n = max(a.n, b.n);
  ans.a.clear();
  ans.a.resize(ans.n + 2, 0);
  for (size_t i = 1; i <= ans.n; ++i) {
    if ((ans.a[i] += (i > a.n ? 0 : a.a[i]) + (i > b.n ? 0 : b.a[i])) >= M)
      ans.a[i] -= M, ans.a[i + 1] = 1;
  }
  ans.n += ans.a[ans.n + 1];
}

void sub(BigInt &ans, const BigInt &a, const BigInt &b) {
  ans.n = a.n;
  ans.a.clear();
  ans.a.resize(ans.n + 1);
  for (size_t i = 1; i <= ans.n; ++i) {
    if ((ans.a[i] += (i > a.n ? 0 : a.a[i]) - (i > b.n ? 0 : b.a[i])) < 0)
      ans.a[i] += M, ans.a[i + 1] = -1;
  }
  while (ans.n > 1 && !ans.a[ans.n]) --ans.n;
  ans.a.resize(ans.n + 1);
}

void mul(BigInt &ans, const BigInt &a, const BigInt &b) {
  size_t lim = limit(a.n + b.n - 1), n = 1ull << lim;
  vector<complex> f(1ull << (lim + 1)), g = f;
  vector<long long> buf(a.n + b.n + 1);
  for (size_t i = 1, e = 1ull << lim; i <= e; ++i) {
    f[i - 1].x = (i > a.n ? .0 : a.a[i]);
    g[i - 1].x = (i > b.n ? .0 : b.a[i]);
  }
  omega.resize(n * 2);
  for (size_t i = 1; i <= n; i *= 2) {
    for (size_t j = 0; j < i; ++j) {
      double deg = PI2 * j / i;
      omega[i | j] = complex(cos(deg), sin(deg));
    }
  }
  FFT(f, g, lim, 1);
  for (size_t i = 0, e = 1ull << lim; i < e; ++i) f[i] = f[i] * g[i];
  FFT(f, lim, -1);
  ans.n = a.n + b.n - 1;
  buf[1] = buf[ans.n + 1] = 0;
  for (size_t i = 1; i <= ans.n; ++i) {
    buf[i + 1] = (buf[i] += (long long)(f[i - 1].x + .5)) / M;
    buf[i] %= M;
  }
  ans.a.resize(ans.n + 2);
  for (size_t i = 1; i <= ans.n + 1; ++i) ans.a[i] = buf[i];
  ans.n += !!ans.a[ans.n + 1];
}

void div_force(BigInt &ans, const BigInt &a, const BigInt &b) {
  BigInt x = b, y = 1, t;
  stack<pair<BigInt, BigInt>> s;
  while (cmp(x, a) <= 0) {
    s.emplace(x, y);
    add(t, x, x);
    x = t;
    add(t, y, y);
    y = t;
  }
  x = a;
  for (ans = 0; s.size(); s.pop()) {
    if (cmp(s.top().first, x) <= 0) {
      sub(t, x, s.top().first), x = t;
      add(t, ans, s.top().second), ans = t;
    }
  }
}

void shift(BigInt &a, long long shift) {
  if (shift >= 0) {
    a.a.resize(a.n + shift + 1);
    for (size_t i = a.n; i >= 1; --i) a.a[i + shift] = a.a[i];
    for (long long i = 1; i <= shift; ++i) a.a[i] = 0;
    a.n += shift;
  } else {
    shift = -shift;
    for (size_t i = 1; i <= a.n - shift; ++i) a.a[i] = a.a[i + shift];
    a.n -= shift;
    a.a.resize(a.n + 1);
  }
}

void sadd(BigInt &a) {
  a.a.resize(a.n + 2);
  for (size_t i = 1;; ++i) {
    if (a.a[i] != M - 1) { ++a.a[i]; break; }
    a.a[i] = 0;
  }
  a.n += !!a.a[a.n + 1];
}

void ssub(BigInt &a) {
  for (size_t i = 1;; ++i) {
    if (!a.a[i]) a.a[i] = M - 1;
    else { --a.a[i]; break; }
  }
  while (a.n > 1 && !a.a[a.n]) --a.n;
  a.a.resize(a.n + 1);
}

void inv(BigInt &ans, const BigInt &a) {
  if (a.n <= 10) {
    BigInt b;
    b.a.resize((b.n = a.n * 2 + 1) + 1);
    b.a[b.n] = 1;
    div_force(ans, b, a);
    return;
  } else {
    BigInt b, c, d;
    size_t m = a.n, k = (a.n + 5) >> 1;
    b.n = k;
    b.a.resize(b.n + 1);
    for (size_t i = b.n, j = a.n; i; b.a[i--] = a.a[j--]);
    inv(c, b); mul(b, a, c); mul(d, b, c);
    shift(d, - 2 * k); add(b, c, c); shift(b, m - k);
    sub(ans, b, d); ssub(ans);
    d.a.clear();
    d.a.resize((d.n = m * 2 + 1) + 1);
    d.a[d.n] = 1;
    mul(b, ans, a); sub(c, d, b);
    if (cmp(c, a) >= 0) sadd(ans);
  }
}

void div(BigInt &ans, const BigInt &a, const BigInt &b) {
  if (a.n < b.n) return void(ans = 0);
  BigInt x = a, y = b, z;
  size_t n = x.n, m = y.n;
  if (n > (m << 1)) {
    shift(x, n - (m << 1));
    shift(y, n - (m << 1));
    m = n - m;
    n = m << 1;
  }
  inv(z, y); mul(y, x, z);
  shift(y, -(m * 2));
  mul(x, b, y); sub(z, a, x);
  if (cmp(z, b) >= 0) sadd(y);
  ans = y;
}

bool operator<(const BigInt& x, const BigInt& y) { return cmp(x, y) == -1; }
bool operator==(const BigInt& x, const BigInt& y) { return cmp(x, y) == 0; }
bool operator>(const BigInt& x, const BigInt& y) { return cmp(x, y) == 1; }
bool operator<=(const BigInt& x, const BigInt& y) { return cmp(x, y) != 1; }
bool operator>=(const BigInt& x, const BigInt& y) { return cmp(x, y) != -1; }
BigInt operator+(const BigInt& x, const BigInt& y) { BigInt z; add(z, x, y); return z; }
BigInt& operator+=(BigInt& x, const BigInt& y) { return x = x + y; }
BigInt& operator++(BigInt& x) { return x = x + 1; }
BigInt operator-(const BigInt& x, const BigInt& y) { BigInt z; sub(z, x, y); return z; }
BigInt& operator-=(BigInt& x, const BigInt& y) { return x = x - y; }
BigInt& operator--(BigInt& x) { return x = x - 1; }
BigInt operator*(const BigInt& x, const BigInt& y) { BigInt z; mul(z, x, y); return z; }
BigInt& operator*=(BigInt& x, const BigInt& y) { return x = x * y; }
BigInt operator/(const BigInt& x, const BigInt& y) { BigInt z; div(z, x, y); return z; }
BigInt& operator/=(BigInt& x, const BigInt& y) { return x = x / y; }
}

namespace _Head {
constexpr size_t BUF = 21727;
char ibuf[BUF], obuf[BUF];
char *li, *ri, *lo = obuf, *ro = obuf + BUF, st[100], *tp = st;
FILE *Istream = stdin, *Ostream = stdout;

char GC() {
#if _CONSOLE
  return getchar();
#endif
  if (li == ri) {
    li = ibuf; ri = li + fread(li, 1, BUF, Istream);
    if (li == ri) return '\n';
  }
  return *li++;
}

void flush() {
  fwrite(obuf, 1, lo - obuf, Ostream);
  lo = obuf;
}

void PC(char ch) {
#if _CONSOLE
  return (void)putchar(ch);
#endif
#ifdef EFILE
  if (lo == ro) flush();
  *lo++ = ch;
  return;
#endif
#ifdef _LOCAL
  return (void)putchar(ch);
#endif
  if (lo == ro) flush();
  *lo++ = ch;
}

template <typename Type>
void r_int(Type& x) {
  bool neg = 0;
  char ch = GC();
  while (ch < 48 || ch > 57) { neg ^= ch == 45; ch = GC(); }
  for (x = 0; ch >= '0' && ch <= '9'; ch = GC()) x = x * 10 + (ch & 15);
  if (neg) x = -x;
}

template <typename Type>
void r_uint(Type& x) {
  char ch = GC();
  while (ch < 48 || ch > 57) ch = GC();
  for (x = 0; ch >= '0' && ch <= '9'; ch = GC()) x = x * 10 + (ch & 15);
}

template <typename Type>
void w_uint(Type x) {
  if (!x) { PC('0'); return; }
  while (x) { *tp++ = x % 10; x /= 10; }
  while (tp > st) PC(*--tp ^ 48);
}

template <typename Type>
void w_int(Type x) {
  if (x < 0) { PC('-'); w_uint(-x); }
  else w_uint(x);
}

struct IO {
  IO& operator>>(char& x) { do { x = GC(); } while (x == 32 || x == 10 || x == 13); return *this; }
  IO& operator>>(string& x) {
    char c;
    operator>>(c);
    x = c;
    for (c = GC(); c != 32 && c != 10 && c != 13; c = GC()) x.push_back(c);
    x.shrink_to_fit();
    return *this;
  }
  IO& operator>>(short& x) { r_int(x); return *this; }
  IO& operator>>(int& x) { r_int(x); return *this; }
  IO& operator>>(long& x) { r_int(x); return *this; }
  IO& operator>>(long long& x) { r_int(x); return *this; }
  IO& operator>>(unsigned short& x) { r_uint(x); return *this; }
  IO& operator>>(unsigned int& x) { r_uint(x); return *this; }
  IO& operator>>(unsigned long& x) { r_uint(x); return *this; }
  IO& operator>>(unsigned long long& x) { r_uint(x); return *this; }
  IO& operator>>(BigInteger::BigInt &a) {
    string s;
    operator>>(s);
    a.n = 0;
    a.a.resize(1);
    for (long long i = s.size() - 1, j = M; i >= 0; j *= 10) {
      if (j == M) { a.a.push_back(0); ++a.n; j = 1; }
      a.a[a.n] += j * (s[i--] & 15);
    }
    return *this;
  }

  IO& operator<<(short x) { w_int(x); return *this; }
  IO& operator<<(int x) { w_int(x); return *this; }
  IO& operator<<(long x) { w_int(x); return *this; }
  IO& operator<<(long long x) { w_int(x); return *this; }
  IO& operator<<(unsigned short x) { w_uint(x); return *this; }
  IO& operator<<(unsigned int x) { w_uint(x); return *this; }
  IO& operator<<(unsigned long x) { w_uint(x); return *this; }
  IO& operator<<(unsigned long long x) { w_uint(x); return *this; }
  IO& operator<<(char x) { PC(x); return *this; }
  IO& operator<<(const string& x) { for (auto& i : x) PC(i); return *this; }
  IO& operator<<(const BigInteger::BigInt& x) {
    operator<<(x.a[x.n]);
    for (size_t i = x.n - 1; i >= 1; --i) {
      string s = to_string(x.a[i]);
      while (s.size() != DIGIT) s = '0' + s;
      operator<<(s);
    }
    return *this;
  }
  
  IO() {
#ifdef EFILE
    Istream = fopen(EFILE ".in", "r");
    Ostream = fopen(EFILE ".out", "w");
#else
#ifdef _LOCAL
    Istream = fopen("input.txt", "r");
    Ostream = fopen("a.out", "w");
#endif
#endif
  }

  ~IO() { flush(); }
} bin;

template <typename Type>
Type qpow(Type x, Type y, Type mod) {
  Type tar = 1;
  while (y) {
    if (y % 2 == 0) tar = tar * x % mod;
    x = x * x % mod;
    y /= 2;
  }
  return tar;
}
template <typename Type>
Type inverse(Type x, Type mod) { return qpow(x, mod - 2, mod); }
}

using _Head::bin, _Head::qpow, _Head::inverse;
using namespace BigInteger;

// :/

void STRUGGLING([[maybe_unused]] tp TEST_NUMBER) {
  BigInt a, b;
  bin >> a >> b;
  bin << a / b << '\n';
}

void MIST() {
}

#include <fstream>

signed main() {
  tp t = 0, _t = 1;
  MIST();
#if _MULTI_TESTS
  cin >> _t;
#endif
  while (t < _t) STRUGGLING(++t);
  return 0;
}

//*/

CompilationN/AN/ACompile OKScore: N/A

Testcase #12.527 ms744 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 11:13:12 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用