結果

問題 No.1396 Giri
コンテスト
ユーザー ninoinui
提出日時 2021-02-14 21:44:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 845 ms / 2,000 ms
コード長 5,647 bytes
コンパイル時間 2,122 ms
コンパイル使用メモリ 209,168 KB
最終ジャッジ日時 2025-01-18 20:51:27
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template <class A, class B> bool cmin(A& a, B b) { return a > b && (a = b, true); }
template <class A, class B> bool cmax(A& a, B b) { return a < b && (a = b, true); }

template <unsigned int& mod> class modint {
private:
  unsigned int v;
  static unsigned int norm(const unsigned int& x) { return x < mod ? x : x - mod; }
  static modint make(const unsigned int& x) {
    modint m;
    return m.v = x, m;
  }
  static modint inv(const modint& x) { return make(inverse(x.v, mod)); }
  static unsigned int inverse(int a, int m) {
    int u[] = {a, 1, 0}, v[] = {m, 0, 1}, t;
    while (*v) {
      t = *u / *v;
      swap(u[0] -= t * v[0], v[0]), swap(u[1] -= t * v[1], v[1]), swap(u[2] -= t * v[2], v[2]);
    }
    return (u[1] % m + m) % m;
  }

public:
  modint() : v{0} {}
  modint(const long val) : v{norm(val % mod + mod)} {}
  modint(const modint<mod>& n) : v{n()} {}
  explicit operator bool() const noexcept { return v != 0; }
  bool operator!() const noexcept { return !static_cast<bool>(*this); }
  modint& operator=(const modint& n) { return v = n(), (*this); }
  modint& operator=(const long val) { return v = norm(val % mod + mod), (*this); }
  modint operator+() const { return *this; }
  modint operator-() const { return v == 0 ? make(0) : make(mod - v); }
  modint operator+(const modint& val) const { return make(norm(v + val())); }
  modint operator-(const modint& val) const { return make(norm(v + mod - val())); }
  modint operator*(const modint& val) const { return make((long)v * val() % mod); }
  modint operator/(const modint& val) const { return *this * inv(val); }
  modint& operator+=(const modint& val) { return *this = *this + val; }
  modint& operator-=(const modint& val) { return *this = *this - val; }
  modint& operator*=(const modint& val) { return *this = *this * val; }
  modint& operator/=(const modint& val) { return *this = *this / val; }
  modint operator+(const long val) const { return modint{v + val}; }
  modint operator-(const long val) const { return modint{v - val}; }
  modint operator*(const long val) const { return modint{(long)(v * (val % mod))}; }
  modint operator/(const long val) const { return modint{(long)v * inv(val)}; }
  modint& operator+=(const long val) { return *this = *this + val; }
  modint& operator-=(const long val) { return *this = *this - val; }
  modint& operator*=(const long val) { return *this = *this * val; }
  modint& operator/=(const long val) { return *this = *this / val; }
  bool operator==(const modint& val) const { return v == val.v; }
  bool operator!=(const modint& val) const { return !(*this == val); }
  bool operator==(const long val) const { return v == norm(val % mod + mod); }
  bool operator!=(const long val) const { return !(*this == val); }
  unsigned int operator()() const { return v; }
  friend modint operator+(const long val, const modint& n) { return n + val; }
  friend modint operator-(const long val, const modint& n) { return modint{val - n()}; }
  friend modint operator*(const long val, const modint& n) { return n * val; }
  friend modint operator/(const long val, const modint& n) { return modint{val} / n; }
  friend bool operator==(const long val, const modint& n) { return n == val; }
  friend bool operator!=(const long val, const modint& n) { return !(val == n); }
  friend istream& operator>>(istream& is, modint& n) {
    unsigned int v;
    return is >> v, n = v, is;
  }
  friend ostream& operator<<(ostream& os, const modint& n) { return (os << n()); }
  friend modint mod_pow(modint x, long n) {
    modint ret = 1;
    while (n) {
      if (n & 1) ret *= x;
      x *= x, n >>= 1;
    }
    return ret;
  }
  friend modint mod_com(modint n, long r) {
    if (n() < r || n() < 0 || r < 0) return modint(0);
    modint x = 1, y = 1;
    for (int i = 1; i <= r; i++) {
      x = x * (n - i + 1);
      y = y * i;
    }
    return x * mod_pow(y, mod - 2);
  }
  friend modint get_inv(modint n) { return inv(n); }
  unsigned int get_mod() { return mod; }
};

template <typename T> class BiCoef {
private:
  int MX;
  vector<T> fact, finv, inv;

public:
  BiCoef(int mx) : MX(mx + 1), fact(MX), finv(MX), inv(MX) {
    int mod = T().get_mod();
    fact.at(0) = fact.at(1) = 1;
    finv.at(0) = finv.at(1) = 1;
    inv.at(1) = 1;
    for (int i = 2; i < MX; i++) {
      fact.at(i) = fact.at(i - 1) * i;
      inv.at(i) = mod - inv.at(mod % i) * (mod / i);
      finv.at(i) = finv.at(i - 1) * inv.at(i);
    }
  }
  T com(long n, long r) {
    if (n < r || n < 0 || r < 0) return 0;
    return fact.at(n) * (finv.at(r) * finv.at(n - r));
  }
};

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  // static unsigned int MOD = 1000000007;
  static unsigned int MOD = 998244353;
  using mint = modint<MOD>;

  int N;
  cin >> N;

  auto pfa = [&](int n) {
    vector<bool> isp(n + 1, true);
    vector<vector<pair<int, int>>> ret(n + 1);
    isp.at(0) = isp.at(1) = false;
    for (int i = 2; i <= n; i++) {
      if (isp.at(i)) {
        ret.at(i).push_back({i, 1});
        for (int j = i * 2; j <= n; j += i) {
          isp.at(j) = false;
          int tmp = j, cnt = 0;
          while (tmp % i == 0) tmp /= i, cnt++;
          ret.at(j).push_back({i, cnt});
        }
      }
    }
    return ret;
  };

  auto PF = pfa(N);

  map<int, int> MA;
  for (int i = N, b = 1; i >= 1; i--) {
    auto pf = PF.at(i);
    if ((int)pf.size() == 1 && pf.front().second == 1 && b) {
      b = 0;
      continue;
    }
    for (const auto& [a, b] : pf) cmax(MA[a], b);
  }

  mint ans = 1;
  for (const auto& [a, b] : MA) ans *= mod_pow((mint)a, b);
  cout << ans << '\n';
}
0