結果

問題 No.858 わり算
ユーザー risujirohrisujiroh
提出日時 2019-08-09 22:00:43
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 7,887 bytes
コンパイル時間 2,236 ms
コンパイル使用メモリ 189,220 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 07:40:52
合計ジャッジ時間 2,741 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 18 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 18 ms
5,376 KB
testcase_05 AC 18 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:197:12: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  197 |   Bint pow(auto n) const {
      |            ^~~~
main.cpp:203:25: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  203 |   friend Bint operator*(auto l, const Bint& r) { return Bint(l) *= r; }
      |                         ^~~~
main.cpp:204:25: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  204 |   friend Bint operator/(auto l, const Bint& r) { return Bint(l) /= r; }
      |                         ^~~~
main.cpp:205:25: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  205 |   friend Bint operator%(auto l, const Bint& r) { return Bint(l) %= r; }
      |                         ^~~~
main.cpp:206:25: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  206 |   friend Bint operator+(auto l, const Bint& r) { return Bint(l) += r; }
      |                         ^~~~
main.cpp:207:25: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  207 |   friend Bint operator-(auto l, const Bint& r) { return Bint(l) -= r; }
      |                         ^~~~
main.cpp:210:25: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  210 |   friend bool operator<(auto l, const Bint& r) { return Bint(l) < r; }
      |                         ^~~~
main.cpp:211:25: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  211 |   friend bool operator>(auto l, const Bint& r) { return r < l; }
      |                         ^~~~
main.cpp:212:26: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  212 |   friend bool operator<=(auto l, const Bint& r) { return !(l > r); }
      |

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

using R = double;
constexpr R pi = acos((R)-1);
using C = complex<R>;
C& operator*=(C& l, const C& r) {
  return l = {real(l) * real(r) - imag(l) * imag(r), real(l) * imag(r) + imag(l) * real(r)};
}
void fft(V<C>& a, bool inv = false) {
  int n = a.size();
  int j = 0;
  for (int i = 1; i < n; ++i) {
    int w = n >> 1;
    while (j >= w) j -= w, w >>= 1;
    j += w;
    if (i < j) swap(a[i], a[j]);
  }
  static VV<C> xi(30);
  for (int k = 0; 1 << k < n; ++k) if (xi[k].empty()) {
    xi[k].resize(1 << k);
    for (int i = 0; i < 1 << k; ++i) {
      xi[k][i] = polar<R>(1, i * pi / (1 << k));
    }
  }
  for (int k = 0; 1 << k < n; ++k) {
    const int w = 1 << k;
    for (int s = 0; s < n; s += 2 * w) {
      for (int i = s; i < s + w; ++i) {
        j = i + w;
        a[j] *= inv ? conj(xi[k][i - s]) : xi[k][i - s];
        tie(a[i], a[j]) = make_pair(a[i] + a[j], a[i] - a[j]);
      }
    }
  }
}
template<int K = 15> void multiply(V<lint>& a, const V<lint>& b) {
  if (a.empty() or b.empty()) {
    a = {};
    return;
  }
  int n = 1 << __lg(2 * (a.size() + b.size() - 1) - 1);
  V<C> f(n), g(n);
  for (int i = 0; i < n; ++i) {
    if (i < (int)a.size()) f[i].real(a[i] & ~(~0 << K)), f[i].imag(a[i] >> K);
    if (i < (int)b.size()) g[i].real(b[i] & ~(~0 << K)), g[i].imag(b[i] >> K);
  }
  fft(f), fft(g);
  V<C> Al(n), Au(n), Bl(n), Bu(n);
  for (int i = 0; i < n; ++i) {
    Al[i] = (f[i] + conj(f[-i & n - 1])) / C(2, 0);
    Au[i] = (f[i] - conj(f[-i & n - 1])) / C(0, 2);
    Bl[i] = (g[i] + conj(g[-i & n - 1])) / C(2, 0);
    Bu[i] = (g[i] - conj(g[-i & n - 1])) / C(0, 2);
  }
  for (int i = 0; i < n; ++i) {
    f[i] = Al[i] * Bl[i] + C(0, 1) * Al[i] * Bu[i];
    g[i] = Au[i] * Bl[i] + C(0, 1) * Au[i] * Bu[i];
  }
  fft(f, true), fft(g, true);
  a.resize(a.size() + b.size() - 1);
  for (int i = 0; i < (int)a.size(); ++i) {
    lint l = real(f[i]) / n + 0.5;
    lint m = (imag(f[i]) + real(g[i])) / n + 0.5;
    lint u = imag(g[i]) / n + 0.5;
    a[i] = l + (m << K) + (u << 2 * K);
  }
}

struct Bint {
  bool neg;
  string s;
  Bint() : neg(false), s("0") {}
  Bint(const string& x) : neg(x[0] == '-'), s(x.substr(neg)) {
    assert(!s.empty() and all_of(begin(s), end(s), [](char c) { return isdigit(c); }));
    s = s.substr(min(s.find_first_not_of('0'), s.size() - 1));
  }
  Bint(lint x) : neg(x < 0), s(to_string(abs(x))) {}
  Bint(bool neg, const string& s) : neg(neg), s(s) {}
  Bint operator+() const { return *this; }
  Bint operator-() const { return {!neg, s}; }
  explicit operator bool() const noexcept { return s != "0"; }
  bool operator!() const noexcept { return !(bool)*this; }
  Bint operator*(const Bint& r) const { return Bint(*this) *= r; }
  Bint operator/(const Bint& r) const { return Bint(*this) /= r; }
  Bint operator%(const Bint& r) const { return Bint(*this) %= r; }
  Bint operator+(const Bint& r) const { return Bint(*this) += r; }
  Bint operator-(const Bint& r) const { return Bint(*this) -= r; }
  bool operator<(const Bint& r) const {
    if (neg != r.neg) return neg;
    return neg ^ make_pair(s.size(), s) < make_pair(r.s.size(), r.s);
  }
  bool operator>(const Bint& r) const { return r < *this; }
  bool operator<=(const Bint& r) const { return !(*this > r); }
  bool operator>=(const Bint& r) const { return !(*this < r); }
  bool operator==(const Bint& r) const { return neg == r.neg and s == r.s; }
  bool operator!=(const Bint& r) const { return !(*this == r); }
  Bint& operator*=(const Bint& r) {
    if (!*this or !r) {
      neg = false, s = "0";
      return *this;
    }
    neg ^= r.neg;
    auto t = r.s;
    if (s.size() + t.size() < 20) {
      s = to_string(stoull(s) * stoull(t));
      return *this;
    }
    constexpr int D = 6, B = 1e6;
    V<lint> a;
    for (int i = s.size(); i > 0; i -= D) {
      a.push_back(stoi(s.substr(max(i - D, 0), min(D, i))));
    }
    V<lint> b;
    for (int i = t.size(); i > 0; i -= D) {
      b.push_back(stoi(t.substr(max(i - D, 0), min(D, i))));
    }
    multiply(a, b);
    V<> res;
    lint c = 0;
    for (int i = 0; i < (int)a.size(); ++i) {
      res.push_back((c += a[i]) % B);
      c /= B;
    }
    s = to_string(c);
    while (!res.empty()) {
      auto t = to_string(res.back());
      while (t.size() < D) t = '0' + t;
      s += t;
      res.pop_back();
    }
    s = s.substr(s.find_first_not_of('0'));
    return *this;
  }
  Bint& operator/=(const Bint& r) {
    assert(r);
    auto t = r.s;
    if (Bint(s) < Bint(t)) {
      neg = false, s = "0";
      return *this;
    }
    neg ^= r.neg;
    string res;
    for (int i = s.size() - t.size(); i >= 0; --i) {
      char c = '0';
      while (Bint(s) >= Bint(t + string(i, '0'))) {
        s = (Bint(s) - Bint(t + string(i, '0'))).s;
        ++c;
      }
      res += c;
    }
    s = res;
    s = s.substr(s.find_first_not_of('0'));
    return *this;
  }
  Bint& operator%=(const Bint& r) { return *this -= *this / r * r; }
  Bint& operator+=(const Bint& r) {
    auto t = r.s;
    reverse(begin(s), end(s));
    reverse(begin(t), end(t));
    while (s.size() < t.size()) s += '0';
    while (t.size() < s.size()) t += '0';
    s += '0', t += '0';
    if (neg == r.neg) {
      int c = 0;
      for (int i = 0; i < (int)s.size(); ++i) {
        if ((s[i] += t[i] - '0' + c) > '9') {
          s[i] -= 10;
          c = 1;
        } else c = 0;
      }
    } else {
      if (neg) swap(s, t);
      s.back() = '1';
      int c = 0;
      for (int i = 0; i < (int)s.size(); ++i) {
        if ((s[i] -= t[i] - '0' + c) < '0') {
          s[i] += 10;
          c = 1;
        } else c = 0;
      }
      if (neg = s.back() == '0') {
        int i = 0;
        while (s[i] == '0') ++i;
        s[i] = '0' + 10 - (s[i] - '0');
        while (++i < (int)s.size() - 1) s[i] = '9' - (s[i] - '0');
      } else s.back() = '0';
    }
    while (s.size() > 1 and s.back() == '0') s.pop_back();
    reverse(begin(s), end(s));
    return *this;
  }
  Bint& operator-=(const Bint& r) { return *this += -r; }
  Bint pow(auto n) const {
    assert(n >= 0);
    Bint res = 1;
    for (Bint a = *this; n; a *= a, n >>= 1) if (n & 1) res *= a;
    return res;
  }
  friend Bint operator*(auto l, const Bint& r) { return Bint(l) *= r; }
  friend Bint operator/(auto l, const Bint& r) { return Bint(l) /= r; }
  friend Bint operator%(auto l, const Bint& r) { return Bint(l) %= r; }
  friend Bint operator+(auto l, const Bint& r) { return Bint(l) += r; }
  friend Bint operator-(auto l, const Bint& r) { return Bint(l) -= r; }
  friend ostream& operator<<(ostream& os, const Bint& r) { if (r.neg) os << '-'; return os << r.s; }
  friend istream& operator>>(istream& is, Bint& r) { string x; is >> x; r = x; return is; }
  friend bool operator<(auto l, const Bint& r) { return Bint(l) < r; }
  friend bool operator>(auto l, const Bint& r) { return r < l; }
  friend bool operator<=(auto l, const Bint& r) { return !(l > r); }
  friend bool operator>=(auto l, const Bint& r) { return !(l < r); }
  friend bool operator==(auto l, const Bint& r) { return Bint(l) == r; }
  friend bool operator!=(auto l, const Bint& r) { return !(l == r); }
};

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int x, y; cin >> x >> y;
  Bint a = x, b = y;
  a.s += string(1000, '0');
  a /= b;
  int q = x / y;
  if (!q) {
    string res;
    stringstream ss;
    ss << fixed << setprecision(15) << (double)x / y;
    for (char c : ss.str()) {
      if (c != '0' and c != '.') break;
      res += c;
    }
    res += a.s.substr(0, 52 - res.size());
    assert(res.substr(0, 2) == "0." and res.size() == 52);
    cout << res << '\n';
  } else {
    auto res = to_string(q);
    res += '.' + a.s.substr(res.size(), 50);
    cout << res << '\n';
  }
}
0