結果

問題 No.551 夏休みの思い出（２）
ユーザー rsk0315rsk0315
提出日時 2019-12-02 16:47:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 71 ms / 4,000 ms
コード長 7,538 bytes
コンパイル時間 741 ms
コンパイル使用メモリ 61,740 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-24 11:29:00
合計ジャッジ時間 2,706 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 6 ms
5,248 KB
testcase_06 AC 6 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 33 ms
5,248 KB
testcase_28 AC 15 ms
5,248 KB
testcase_29 AC 26 ms
5,248 KB
testcase_30 AC 51 ms
5,248 KB
testcase_31 AC 14 ms
5,248 KB
testcase_32 AC 42 ms
5,248 KB
testcase_33 AC 16 ms
5,248 KB
testcase_34 AC 28 ms
5,248 KB
testcase_35 AC 14 ms
5,248 KB
testcase_36 AC 15 ms
5,248 KB
testcase_37 AC 17 ms
5,248 KB
testcase_38 AC 37 ms
5,248 KB
testcase_39 AC 16 ms
5,248 KB
testcase_40 AC 16 ms
5,248 KB
testcase_41 AC 71 ms
5,248 KB
testcase_42 AC 17 ms
5,248 KB
testcase_43 AC 16 ms
5,248 KB
testcase_44 AC 16 ms
5,248 KB
testcase_45 AC 16 ms
5,248 KB
testcase_46 AC 31 ms
5,248 KB
testcase_47 AC 2 ms
5,248 KB
testcase_48 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
In static member function 'static modint<Tp, Modulo>::value_type modint<Tp, Modulo>::S_normalize(value_type, value_type) [with Tp = long int; Tp Modulo = 0]',
    inlined from 'modint<Tp, Modulo>::modint(const modint<Tp, Modulo>&, value_type) [with Tp = long int; Tp Modulo = 0]' at main.cpp:82:24,
    inlined from 'modint<Tp, Modulo> modint<Tp, Modulo>::pow(intmax_t) const [with Tp = long int; Tp Modulo = 0]' at main.cpp:141:12,
    inlined from 'std::vector<modint<Tp, Modulo> > modint<Tp, Modulo>::sqrt() const [with Tp = long int; Tp Modulo = 0]' at main.cpp:187:21:
main.cpp:61:5: warning: 'z.modint<long int, 0>::M_mod' may be used uninitialized [-Wmaybe-uninitialized]
   61 |     if (n >= m) {
      |     ^~
main.cpp: In member function 'std::vector<modint<Tp, Modulo> > modint<Tp, Modulo>::sqrt() const [with Tp = long int; Tp Modulo = 0]':
main.cpp:180:12: note: 'z.modint<long int, 0>::M_mod' was declared here
  180 |     modint z;
      |            ^

ソースコード

diff # 

#include <cstdio>
#include <cstdint>
#include <climits>
#include <vector>
#include <algorithm>
#include <utility>
#include <type_traits>

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
// constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }

namespace bit {
template <typename Tp>
int log2p1(Tp n) {
  if (n == 0) return 0;
  return (CHAR_BIT * sizeof(long long)) - __builtin_clzll(n);
}

template <typename Tp>
Tp ceil2(Tp n) {
  if (n == 0) return 1;
  return Tp{1} << log2p1(n-1);
}

template <typename Tp>
int ctz(Tp n) {
  return __builtin_ctzll(n);
}
}  // bit::

template <typename Tp, Tp Modulo>
class modint {
  // FIXME to implement with Montgomery multiplication

public:
  using value_type = typename std::make_signed<Tp>::type;

private:
  static constexpr value_type S_mod = Modulo;
  value_type M_value = 0;
  value_type M_mod;  // runtime value (used if S_mod == 0)

  static constexpr value_type S_inv(value_type n, value_type m) {
    value_type x = 0;
    value_type y = 1;
    value_type a = n;
    value_type b = m;
    for (value_type u = y, v = x; a;) {
      value_type q = b / a;
      std::swap(x -= q*u, u);
      std::swap(y -= q*v, v);
      std::swap(b -= q*a, a);
    }
    if ((x %= m) < 0) x += m;
    return x;
  }

  static value_type S_normalize(value_type n, value_type m) {
    if (n >= m) {
      n %= m;
    } else if (n < 0) {
      n %= m;
      n += m;
    }
    return n;
  }

public:
  modint() = default;
  modint(modint const&) = default;
  modint(modint&&) = default;
  template <typename Up = Tp, typename std::enable_if<(Modulo > 0), Up>::type* = nullptr>
  modint(value_type n):
    M_value(S_normalize(n, Modulo)) {}
  template <typename Up = Tp, typename std::enable_if<(Modulo == 0), Up>::type* = nullptr>
  modint(value_type n, value_type m):
    M_value(S_normalize(n, m)), M_mod(m) {}
  // copying mod
  modint(modint const& base, value_type n):
    M_value(S_normalize(n, base.modulo())), M_mod(base.M_mod) {}

  modint& operator =(modint const&) = default;
  modint& operator =(modint&&) = default;
  modint& operator =(value_type n) {
    M_value = S_normalize(n, modulo());
    return *this;
  }

  modint& operator +=(modint const& other) {
    if ((M_value += other.M_value) >= modulo()) M_value -= modulo();
    return *this;
  }
  modint& operator -=(modint const& other) {
    if ((M_value -= other.M_value) < 0) M_value += modulo();
    return *this;
  }
  modint& operator *=(modint const& other) {
    (M_value *= other.M_value) %= modulo();
    return *this;
  }
  modint& operator /=(modint const& other) {
    (M_value *= S_inv(other.M_value, modulo())) %= modulo();
    return *this;
  }

  modint& operator +=(value_type const& n) {
    if ((M_value += S_normalize(n, modulo())) >= modulo()) M_value -= modulo();
    return *this;
  }
  modint& operator -=(value_type const& n) {
    if ((M_value -= S_normalize(n, modulo())) < 0) M_value += modulo();
    return *this;
  }
  modint& operator *=(value_type const& n) {
    (M_value *= S_normalize(n, modulo())) %= modulo();
    return *this;
  }
  modint& operator /=(value_type const& n) {
    (M_value *= S_inv(S_normalize(n, modulo()), modulo())) %= modulo();
    return *this;
  }

  modint operator +(modint const& other) const { return modint(*this) += other; }
  modint operator -(modint const& other) const { return modint(*this) -= other; }
  modint operator *(modint const& other) const { return modint(*this) *= other; }
  modint operator /(modint const& other) const { return modint(*this) /= other; }
  modint operator +(value_type const& n) const { return modint(*this) += n; }
  modint operator -(value_type const& n) const { return modint(*this) -= n; }
  modint operator *(value_type const& n) const { return modint(*this) *= n; }
  modint operator /(value_type const& n) const { return modint(*this) /= n; }

  modint operator +() const { return *this; }
  modint operator -() const {
    if (M_value == 0) return *this;
    return modint(*this, modulo()-M_value);
  }

  modint pow(intmax_t iexp) const {
    modint res(*this, 1);
    for (modint dbl = *this; iexp; iexp >>= 1) {
      if (iexp & 1) res *= dbl;
      dbl *= dbl;
    }
    return res;
  }
  modint& pow_eq(intmax_t iexp) { return *this = this->pow(iexp); }

  bool operator ==(modint const& other) const {
    return M_value == other.M_value;
  }
  bool operator ==(value_type const& n) const {
    return M_value == S_normalize(n, modulo());
  }
  bool operator !=(modint const& other) const { return !(*this == other); }
  bool operator !=(value_type const& n) const { return !(*this == n); }

  value_type get() const { return M_value; }
  value_type modulo() const { return ((S_mod > 0)? S_mod: M_mod); }

  static value_type generator(value_type p) {
    if (p == 998244353) return 3;
    return -1;
  }

  std::vector<modint> sqrt() const {
    if (*this == 0) return {*this};

    intmax_t const p = modulo();
    if (p % 4 == 3) {
      modint r = pow((p+1) / 4);
      if (r * r == *this) return {r, -r};
      return {};
    }

    value_type s = bit::ctz(p-1);
    value_type q = (p-1) >> s;

    modint z;
    for (value_type z0 = 2; z0 < p; ++z0) {
      z = modint(*this, z0);
      if (z.pow((p-1) / 2) == -1) break;
    }

    value_type m = s;
    modint c = z.pow(q);
    modint t = this->pow(q);
    modint r = this->pow((q+1) / 2);

    while (true) {
      if (t == 0) return {modint(*this, 0)};
      if (t == 1) return {r, -r};

      value_type i = 0;
      for (auto tt = t; tt != 1; ++i) tt *= tt;
      if (i == m) return {};
      auto b = c;
      for (value_type j = 0; j < m-i-1; ++j) b *= b;
      m = i;
      c = b * b;
      t *= c;
      r *= b;
    }
  }
};

template <typename T1, typename T2, T2 Modulo>
modint<T2, Modulo> operator +(T1 const& lhs, modint<T2, Modulo> const& rhs) {
  return rhs + lhs;
}
template <typename T1, typename T2, T2 Modulo>
modint<T2, Modulo> operator -(T1 const& lhs, modint<T2, Modulo> const& rhs) {
  return -(rhs - lhs);
}
template <typename T1, typename T2, T2 Modulo>
modint<T2, Modulo> operator *(T1 const& lhs, modint<T2, Modulo> const& rhs) {
  return rhs * lhs;
}
template <typename T1, typename T2, T2 Modulo>
modint<T2, Modulo> operator /(T1 const& lhs, modint<T2, Modulo> const& rhs) {
  return modint<T2, Modulo>(rhs, lhs) / rhs;
}
template <typename T1, typename T2, T2 Modulo>
bool operator ==(T1 const& lhs, modint<T2, Modulo> const& rhs) {
  return rhs == lhs;
}
template <typename T1, typename T2, T2 Modulo>
bool operator !=(T1 const& lhs, modint<T2, Modulo> const& rhs) {
  return !(lhs == rhs);
}

// constexpr intmax_t mod = 1'000'000'007;  // '
// constexpr intmax_t mod = 998244353;
using mi = modint<intmax_t, 0>;

int main() {
  intmax_t p;
  scanf("%jd %*d", &p);

  int q;
  scanf("%d", &q);

  for (int i = 0; i < q; ++i) {
    intmax_t ra, rb, rc;
    scanf("%jd %jd %jd", &ra, &rb, &rc);

    mi a(ra, p);
    mi b(rb, p);
    mi c(rc, p);

    // x = (-b + Sqrt(b*b-4*a*c)) / (2a)
    auto ds = (b*b-4*a*c).sqrt();
    if (ds.empty()) {
      puts("-1");
      continue;
    }
    std::vector<intmax_t> res;
    for (auto d: ds) {
      auto x = (-b+d) / (2*a);
      res.push_back(x.get());
    }
    std::sort(res.begin(), res.end());
    for (size_t i = 0; i < res.size(); ++i)
      printf("%jd%c", res[i], i+1<res.size()? ' ': '\n');
  }
}
0