結果
問題 | No.1529 Constant Lcm |
ユーザー | KoD |
提出日時 | 2021-06-04 21:45:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 229 ms / 3,000 ms |
コード長 | 7,166 bytes |
コンパイル時間 | 2,540 ms |
コンパイル使用メモリ | 210,552 KB |
実行使用メモリ | 20,464 KB |
最終ジャッジ日時 | 2024-11-19 13:36:19 |
合計ジャッジ時間 | 5,723 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,820 KB |
testcase_09 | AC | 2 ms
6,816 KB |
testcase_10 | AC | 205 ms
19,648 KB |
testcase_11 | AC | 72 ms
10,716 KB |
testcase_12 | AC | 5 ms
6,820 KB |
testcase_13 | AC | 176 ms
18,768 KB |
testcase_14 | AC | 104 ms
11,772 KB |
testcase_15 | AC | 119 ms
16,704 KB |
testcase_16 | AC | 86 ms
11,076 KB |
testcase_17 | AC | 44 ms
7,296 KB |
testcase_18 | AC | 47 ms
7,424 KB |
testcase_19 | AC | 109 ms
11,976 KB |
testcase_20 | AC | 225 ms
20,464 KB |
testcase_21 | AC | 219 ms
20,456 KB |
testcase_22 | AC | 218 ms
20,336 KB |
testcase_23 | AC | 221 ms
20,332 KB |
testcase_24 | AC | 229 ms
20,328 KB |
testcase_25 | AC | 225 ms
20,332 KB |
ソースコード
#include <bits/stdc++.h> using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; using isize = std::ptrdiff_t; using usize = std::size_t; class rep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { ++itr; } constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; } constexpr usize operator*() const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {} constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; constexpr u64 ceil_log2(const u64 x) { u64 e = 0; while (((u64)1 << e) < x) ++e; return e; } template <class F> class AutoReallocation { using R = typename decltype(std::declval<F>()((usize)0))::value_type; F func; mutable std::vector<R> data; public: explicit AutoReallocation(F&& f) : func(std::forward<F>(f)), data() {} void reserve(const usize size) const { if (data.size() < size) data = func(((usize)1 << ceil_log2(size))); } R operator[](const usize i) const { reserve(i + 1); return data[i]; } }; template <class F> decltype(auto) auto_realloc(F&& f) { using G = std::decay_t<F>; return AutoReallocation<G>(std::forward<G>(f)); } struct PrimeSieve { static inline const auto min_prime = auto_realloc([](const usize n) { std::vector<usize> ret(n); std::iota(ret.begin(), ret.end(), (usize)0); std::vector<usize> list; for (const usize i : rep(2, n)) { if (ret[i] == i) list.push_back(i); for (const usize p : list) { if (p * i >= n || p > ret[i]) break; ret[p * i] = p; } } return ret; }); static bool is_prime(const usize n) { if (n <= 1) return false; return min_prime[n] == n; } template <class T> static std::vector<std::pair<T, usize>> factorize(T x) { assert(x > 0); std::vector<std::pair<T, usize>> ret; while (x != 1) { const usize p = min_prime[x]; ret.emplace_back((T)p, 0); while (min_prime[x] == p) { ret.back().second++; x /= p; } } return ret; } }; template <class T> bool setmax(T& lhs, const T& rhs) { if (lhs < rhs) { lhs = rhs; return true; } return false; } template <class T> constexpr T totient(T x) { T ret = x; for (T i = 2; i * i <= x; ++i) { if (x % i == 0) { ret /= i; ret *= i - 1; while (x % i == 0) x /= i; } } if (x > 1) { ret /= x; ret *= x - 1; } return ret; } template <class T> constexpr T rem_euclid(T value, const T& mod) { return (value %= mod) >= 0 ? value : value + mod; } template <u32 MOD, std::enable_if_t<((u32)1 <= MOD and MOD <= ((u32)1 << 31))>* = nullptr> class StaticModint { using Mint = StaticModint; static inline constexpr u32 PHI = totient(MOD); u32 v; public: static constexpr u32 mod() noexcept { return MOD; } template <class T, std::enable_if_t<std::is_signed_v<T> and std::is_integral_v<T>>* = nullptr> static constexpr T normalize(const T x) noexcept { return rem_euclid<std::common_type_t<T, i64>>(x, MOD); } template <class T, std::enable_if_t<std::is_unsigned_v<T> and std::is_integral_v<T>>* = nullptr> static constexpr T normalize(const T x) noexcept { return x % MOD; } constexpr StaticModint() noexcept : v(0) {} template <class T> constexpr StaticModint(const T x) noexcept : v(normalize(x)) {} template <class T> static constexpr Mint raw(const T x) noexcept { Mint ret; ret.v = x; return ret; } constexpr u32 get() const noexcept { return v; } constexpr Mint neg() const noexcept { return raw(v == 0 ? 0 : MOD - v); } constexpr Mint inv() const noexcept { return pow(PHI - 1); } constexpr Mint pow(u64 exp) const noexcept { Mint ret(1), mult(*this); for (; exp > 0; exp >>= 1) { if (exp & 1) ret *= mult; mult *= mult; } return ret; } constexpr Mint operator-() const noexcept { return neg(); } constexpr Mint operator~() const noexcept { return inv(); } constexpr Mint operator+(const Mint& rhs) const noexcept { return Mint(*this) += rhs; } constexpr Mint& operator+=(const Mint& rhs) noexcept { if ((v += rhs.v) >= MOD) v -= MOD; return *this; } constexpr Mint operator-(const Mint& rhs) const noexcept { return Mint(*this) -= rhs; } constexpr Mint& operator-=(const Mint& rhs) noexcept { if (v < rhs.v) v += MOD; v -= rhs.v; return *this; } constexpr Mint operator*(const Mint& rhs) const noexcept { return Mint(*this) *= rhs; } constexpr Mint& operator*=(const Mint& rhs) noexcept { v = (u64)v * rhs.v % MOD; return *this; } constexpr Mint operator/(const Mint& rhs) const noexcept { return Mint(*this) /= rhs; } constexpr Mint& operator/=(const Mint& rhs) noexcept { return *this *= rhs.inv(); } constexpr bool operator==(const Mint& rhs) const noexcept { return v == rhs.v; } constexpr bool operator!=(const Mint& rhs) const noexcept { return v != rhs.v; } friend std::ostream& operator<<(std::ostream& stream, const Mint& rhs) { return stream << rhs.v; } }; using Modint1000000007 = StaticModint<1000000007>; using Modint998244353 = StaticModint<998244353>; template <class T> using Vec = std::vector<T>; using Fp = Modint998244353; void main_() { usize N; std::cin >> N; Vec<usize> max(N); for (const auto i : rep(1, N / 2 + 1)) { const auto left = PrimeSieve::factorize(i); const auto right = PrimeSieve::factorize(N - i); usize l = 0, r = 0; while (l < left.size() or r < right.size()) { if (l < left.size() and r < right.size() and left[l].first == right[r].first) { setmax(max[left[l].first], left[l].second + right[r].second); l += 1; r += 1; } else { if (r == right.size() or (l < left.size() and left[l].first < right[r].first)) { setmax(max[left[l].first], left[l].second); l += 1; } else { setmax(max[right[r].first], right[r].second); r += 1; } } } } Fp ans = 1; for (const auto i : rep(1, N)) { // std::cerr << i << ' ' << max[i] << std::endl; ans *= Fp(i).pow(max[i]); } std::cout << ans << '\n'; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); main_(); return 0; }