結果
問題 | No.2576 LCM Pattern |
ユーザー |
![]() |
提出日時 | 2023-12-09 12:05:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 25,934 bytes |
コンパイル時間 | 3,053 ms |
コンパイル使用メモリ | 260,204 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-27 03:34:26 |
合計ジャッジ時間 | 3,772 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#line 1 "Library/src/debug.hpp"#ifdef ONLINE_JUDGE#define debug(x) void(0)#else#define _GLIBCXX_DEBUG#define debug(x) std::cerr << __LINE__ << " : " << #x << " = " << (x) << std::endl#endif#line 2 "Library/src/math/rho.hpp"#include <algorithm>#include <vector>#line 2 "Library/src/math/gcd.hpp"#include <cassert>#include <tuple>namespace kyopro {template <typename T> constexpr inline T _gcd(T a, T b) noexcept {assert(a >= 0 && b >= 0);if (a == 0 || b == 0) return a + b;int d = std::min<T>(__builtin_ctzll(a), __builtin_ctzll(b));a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b);while (a != b) {if (!a || !b) {return a + b;}if (a >= b) {a -= b;a >>= __builtin_ctzll(a);} else {b -= a;b >>= __builtin_ctzll(b);}}return a << d;}template <typename T> constexpr inline T ext_gcd(T a, T b, T& x, T& y) noexcept {x = 1, y = 0;T nx = 0, ny = 1;while (b) {T q = a / b;std::tie(a, b) = std::pair<T, T>{b, a % b};std::tie(x, nx) = std::pair<T, T>{nx, x - nx * q};std::tie(y, ny) = std::pair<T, T>{ny, y - ny * q};}return a;}}; // namespace kyopro#line 3 "Library/src/math/dynamic_modint.hpp"#include <iostream>#line 2 "Library/src/internal/barrett.hpp"#include <cstdint>namespace kyopro {namespace internal {/*** @brief Barrett Reduction*/class barrett {using u32 = std::uint32_t;using u64 = std::uint64_t;using u128 = __uint128_t;u32 m;u64 im;public:constexpr barrett() : m(0), im(0) {}constexpr barrett(u32 m): m(m), im(static_cast<u64>(-1) / m + 1) {}constexpr u32 get_mod() const { return m; }constexpr u32 reduce(u32 a) const { return mul(1, a); }constexpr u32 mul(u32 a, u32 b) const {u64 z = (u64)a * b;u64 x = (u64)(((u128)(z)*im) >> 64);u64 y = x * m;return (u32)(z - y + (z < y ? m : 0));}};}; // namespace internal}; // namespace kyopro/*** @ref* https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp*/#line 3 "Library/src/internal/montgomery.hpp"#include <limits>#include <numeric>#line 5 "Library/src/internal/type_traits.hpp"#include <typeinfo>#line 7 "Library/src/internal/type_traits.hpp"namespace kyopro {namespace internal {template <typename... Args> struct first_enabled {};template <typename T, typename... Args>struct first_enabled<std::enable_if<true, T>, Args...> {using type = T;};template <typename T, typename... Args>struct first_enabled<std::enable_if<false, T>, Args...>: first_enabled<Args...> {};template <typename T, typename... Args> struct first_enabled<T, Args...> {using type = T;};template <typename... Args>using first_enabled_t = typename first_enabled<Args...>::type;template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least {using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>,std::enable_if<dgt <= 16, std::int16_t>,std::enable_if<dgt <= 32, std::int32_t>,std::enable_if<dgt <= 64, std::int64_t>,std::enable_if<dgt <= 128, __int128_t>>;};template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least {using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>,std::enable_if<dgt <= 16, std::uint16_t>,std::enable_if<dgt <= 32, std::uint32_t>,std::enable_if<dgt <= 64, std::uint64_t>,std::enable_if<dgt <= 128, __uint128_t>>;};template <int dgt> using int_least_t = typename int_least<dgt>::type;template <int dgt> using uint_least_t = typename uint_least<dgt>::type;template <typename T>using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;template <typename T>using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;struct modint_base {};template <typename T> using is_modint = std::is_base_of<modint_base, T>;template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;// is_integraltemplate <typename T>using is_integral_t =std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> ||std::is_same_v<T, __uint128_t>>;}; // namespace internal}; // namespace kyopro/** @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8*/#line 6 "Library/src/internal/montgomery.hpp"namespace kyopro {namespace internal {using u32 = uint32_t;using u64 = uint64_t;using i32 = int32_t;using i64 = int64_t;using u128 = __uint128_t;using i128 = __int128_t;/*** @brief Montgomery Reduction*/template <typename T> class Montgomery {static constexpr int lg = std::numeric_limits<T>::digits;using LargeT = internal::double_size_uint_t<T>;T mod, r, r2, minv;T inv() {T t = 0, res = 0;for (int i = 0; i < lg; ++i) {if (~t & 1) {t += mod;res += static_cast<T>(1) << i;}t >>= 1;}return res;}public:Montgomery() = default;constexpr T get_mod() { return mod; }void set_mod(T m) {assert(m);assert(m & 1);mod = m;r = (-static_cast<T>(mod)) % mod;r2 = (-static_cast<LargeT>(mod)) % mod;minv = inv();}T reduce(LargeT x) const {u64 res =(x + static_cast<LargeT>(static_cast<T>(x) * minv) * mod) >> lg;if (res >= mod) res -= mod;return res;}T generate(LargeT x) { return reduce(x * r2); }T mul(T x, T y) { return reduce((LargeT)x * y); }};}; // namespace internal}; // namespace kyopro#line 6 "Library/src/math/dynamic_modint.hpp"namespace kyopro {template <int id = -1> class barrett_modint : internal::modint_base {using mint = barrett_modint<id>;using u32 = std::uint32_t;using u64 = std::uint64_t;using i32 = std::int32_t;using i64 = std::int64_t;using br = internal::barrett;static br brt;u32 v;public:static void set_mod(u32 mod_) { brt = br(mod_); }public:explicit constexpr barrett_modint() noexcept : v(0) { assert(mod()); }explicit constexpr barrett_modint(i64 v_) noexcept : v() {assert(mod());if (v_ < 0) v_ = (i64)mod() - v_;v = brt.reduce(v_);}u32 val() const noexcept { return v; }static u32 mod() { return brt.get_mod(); }static mint raw(u32 v) {mint x;x.v = v;return x;}constexpr mint& operator++() noexcept {++v;if (v == mod()) v = 0;return (*this);}constexpr mint& operator--() noexcept {if (v == 0) v = mod();--v;return (*this);}constexpr mint operator++(int) noexcept {mint res(*this);++(*this);return res;}constexpr mint operator--(int) noexcept {mint res(*this);--(*this);return res;}constexpr mint& operator+=(const mint& r) noexcept {v += r.v;if (v >= mod()) v -= mod();return (*this);}constexpr mint& operator-=(const mint& r) noexcept {v += mod() - r.v;if (v >= mod()) {v -= mod();}return (*this);}constexpr mint& operator*=(const mint& r) noexcept {v = brt.mul(v, r.v);return (*this);}constexpr mint& operator/=(const mint& r) noexcept {return (*this) *= r.inv();}friend mint operator+(const mint& lhs, const mint& rhs) noexcept {return mint(lhs) += rhs;}friend mint operator-(const mint& lhs, const mint& rhs) noexcept {return mint(lhs) -= rhs;}friend mint operator*(const mint& lhs, const mint& rhs) noexcept {return mint(lhs) *= rhs;}friend mint operator/(const mint& lhs, const mint& rhs) noexcept {return mint(lhs) /= rhs;}friend bool operator==(const mint& lhs, const mint& rhs) noexcept {return lhs.v == rhs.v;}friend bool operator!=(const mint& lhs, const mint& rhs) noexcept {return lhs.v != rhs.v;}constexpr mint& operator+=(i64 r) noexcept { return (*this) += mint(r); }constexpr mint& operator-=(i64 r) noexcept { return (*this) -= mint(r); }constexpr mint& operator*=(i64 r) noexcept { return (*this) *= mint(r); }friend mint operator+(i64 l, const mint& r) noexcept {return mint(l) += r;}friend mint operator+(const mint& l, i64 r) noexcept {return mint(l) += r;}friend mint operator-(i64 l, const mint& r) noexcept {return mint(l) -= r;}friend mint operator-(const mint& l, i64 r) noexcept {return mint(l) -= r;}friend mint operator*(i64 l, const mint& r) noexcept {return mint(l) *= r;}friend mint operator*(const mint& l, i64 r) noexcept {return mint(l) *= r;}constexpr mint operator+() const noexcept { return *this; }constexpr mint operator-() const noexcept { return mint() - *this; }template <typename T> mint pow(T e) const noexcept {mint res(1), base(*this);while (e) {if (e & 1) {res *= base;}e >>= 1;base *= base;}return res;}constexpr mint inv() const noexcept { return pow(mod() - 2); }};}; // namespace kyoprotemplate <int id>typename kyopro::barrett_modint<id>::br kyopro::barrett_modint<id>::brt;namespace kyopro {template <typename T, int id = -1>class montgomery_modint : internal::modint_base {using LargeT = internal::double_size_uint_t<T>;static T _mod;static internal::Montgomery<T> mr;public:static void set_mod(T mod_) {mr.set_mod(mod_);_mod = mod_;}static T mod() { return _mod; }private:T v;public:montgomery_modint(T v_ = 0) {assert(_mod);v = mr.generate(v_);}T val() const { return mr.reduce(v); }using mint = montgomery_modint<T, id>;mint& operator+=(const mint& r) {v += r.v;if (v >= mr.get_mod()) {v -= mr.get_mod();}return (*this);}mint& operator-=(const mint& r) {v += mr.get_mod() - r.v;if (v >= mr.get_mod) {v -= mr.get_mod();}return (*this);}mint& operator*=(const mint& r) {v = mr.mul(v, r.v);return (*this);}mint operator+(const mint& r) { return mint(*this) += r; }mint operator-(const mint& r) { return mint(*this) -= r; }mint operator*(const mint& r) { return mint(*this) *= r; }mint& operator=(const T& v_) {(*this) = mint(v_);return (*this);}friend std::ostream& operator<<(std::ostream& os, const mint& mt) {os << mt.val();return os;}friend std::istream& operator>>(std::istream& is, mint& mt) {T v_;is >> v_;mt = v_;return is;}template <typename P> mint pow(P e) const {assert(e >= 0);mint res(1), base(*this);while (e) {if (e & 1) {res *= base;}e >>= 1;base *= base;}return res;}mint inv() const { return pow(mod() - 2); }mint& operator/=(const mint& r) { return (*this) *= r.inv(); }mint operator/(const mint& r) const { return mint(*this) *= r.inv(); }mint& operator/=(T r) { return (*this) /= mint(r); }friend mint operator/(const mint& l, T r) { return mint(l) /= r; }friend mint operator/(T l, const mint& r) { return mint(l) /= r; }};}; // namespace kyoprotemplate <typename T, int id> T kyopro::montgomery_modint<T, id>::_mod;template <typename T, int id>kyopro::internal::Montgomery<T> kyopro::montgomery_modint<T, id>::mr;/*** @brief dynamic modint*/#line 3 "Library/src/math/miller.hpp"namespace kyopro {class miller {using i128 = __int128_t;using u128 = __uint128_t;using u64 = std::uint64_t;using u32 = std::uint32_t;template <typename T, typename mint, const int bases[], int length>static constexpr bool miller_rabin(T n) {T d = n - 1;while (~d & 1) {d >>= 1;}const T rev = n - 1;if (mint::mod() != n) {mint::set_mod(n);}for (int i = 0; i < length; ++i) {if (n <= bases[i]) {return true;}T t = d;mint y = mint(bases[i]).pow(t);while (t != n - 1 && y.val() != 1 && y.val() != rev) {y *= y;t <<= 1;}if (y.val() != rev && (~t & 1)) return false;}return true;}// 底static constexpr int bases_int[3] = {2, 7, 61};static constexpr int bases_ll[7] = {2, 325, 9375, 28178,450775, 9780504, 1795265022};public:template <typename T> static constexpr bool is_prime(T n) {if (n < 2) {return false;} else if (n == 2) {return true;} else if (~n & 1) {return false;};if constexpr (std::numeric_limits<T>::digits < 32) {return miller_rabin<T, montgomery_modint<std::make_unsigned_t<T>>,bases_int, 3>(n);} else {if (n <= 1 << 30)return miller_rabin<T,montgomery_modint<std::make_unsigned_t<T>>,bases_int, 3>(n);elsereturn miller_rabin<T, montgomery_modint<std::make_unsigned_t<T>>, bases_ll, 7>(n);}return false;}};}; // namespace kyopro/*** @brief MillerRabin素数判定* @docs docs/math/miller.md*/#line 2 "Library/src/random/xor_shift.hpp"#include <chrono>#line 4 "Library/src/random/xor_shift.hpp"#include <random>namespace kyopro {struct xor_shift32 {uint32_t rng;constexpr explicit xor_shift32(uint32_t seed) : rng(seed) {}explicit xor_shift32(): rng(std::chrono::steady_clock::now().time_since_epoch().count()) {}constexpr uint32_t operator()() {rng ^= rng << 13;rng ^= rng >> 17;rng ^= rng << 5;return rng;}};struct xor_shift {uint64_t rng;constexpr explicit xor_shift(uint64_t seed) : rng(seed) {}explicit xor_shift(): rng(std::chrono::steady_clock::now().time_since_epoch().count()) {}constexpr uint64_t operator()() {rng ^= rng << 13;rng ^= rng >> 7;rng ^= rng << 17;return rng;}};}; // namespace kyopro/*** @brief Xor Shift*/#line 7 "Library/src/math/rho.hpp"namespace kyopro {class rho {using i128 = __int128_t;using u128 = __uint128_t;using u64 = uint64_t;using u32 = uint32_t;template <typename T,typename mint> static constexpr T find_factor(T n) {xor_shift32 rng(2023);if (~n & 1uL) {return 2;}if (kyopro::miller::is_prime(n)) {return n;}if (mint::mod() != n) {mint::set_mod(n);}while (1) {T c = rng();const auto f = [&](mint x) -> mint { return x * x + c; };mint x = rng();mint y = f(x);T d = 1;while (d == 1) {d = _gcd<std::make_signed_t<T>>(std::abs((std::make_signed_t<T>)x.val() - (std::make_signed_t<T>)y.val()), n);x = f(x);y = f(f(y));}if (1 < d && d < n) {return d;}}exit(-1);}template <typename T,typename mint> static std::vector<T> rho_fact(T n) {if (n < 2) {return {};}if (kyopro::miller::is_prime(n)) {return {n};}std::vector<T> v;std::vector<T> st{n};while (!st.empty()) {u64 m = st.back();if (kyopro::miller::is_prime(m)) {v.emplace_back(m);st.pop_back();} else {T d = find_factor<T, mint>(m);st.back() /= d;st.emplace_back(d);}}return v;}public:template <typename T> static std::vector<T> factorize(T n) {if (n < 2) {return {};}if constexpr (std::numeric_limits<T>::digits < 32) {std::vector v = rho_fact<T, montgomery_modint<u32>>(n);std::sort(v.begin(), v.end());return v;} else {std::vector v = rho_fact<T, montgomery_modint<u64>>(n);std::sort(v.begin(), v.end());return v;}}template<typename T>static std::vector<std::pair<T, int>> exp_factorize(T n) {std::vector pf = factorize(n);if (pf.empty()) {return {};}std::vector<std::pair<T, int>> res;res.emplace_back(pf.front(), 1);for (int i = 1; i < (int)pf.size(); i++) {if (res.back().first == pf[i]) {res.back().second++;} else {res.emplace_back(pf[i], 1);}}return res;}template<typename T>static std::vector<T> enumerate_divisor(T n) {std::vector<std::pair<T, int>> pf = rho::exp_factorize(n);std::vector<T> divisor{1};for (auto [p, e] : pf) {u64 pow = p;int sz = divisor.size();for (int i = 0; i < e; ++i) {for (int j = 0; j < sz; ++j)divisor.emplace_back(divisor[j] * pow);pow *= p;}}return divisor;}};}; // namespace kyopro/*** @brief PollardRho素因数分解* @docs docs/math/rho.md*/#line 5 "Library/src/math/static_modint.hpp"#line 8 "Library/src/math/static_modint.hpp"namespace kyopro {template <int _mod, std::enable_if_t<_mod >= 0>* = nullptr>class modint : internal::modint_base {using mint = modint<_mod>;using i32 = std::int32_t;using u32 = std::uint32_t;using i64 = std::int64_t;using u64 = std::uint64_t;u32 v;constexpr u32 normalize(i64 v_) const noexcept {v_ %= _mod;if (v_ < 0) {v_ += _mod;}return v_;}public:static constexpr u32 mod() noexcept { return _mod; }constexpr modint() noexcept : v(0) {}constexpr modint(i64 v_) noexcept : v(normalize(v_)) {}static mint raw(u32 a) {mint m;m.v = a;return m;}constexpr u32 val() const noexcept { return v; }constexpr mint& operator+=(const mint& rhs) noexcept {v += rhs.val();if (v >= _mod) {v -= _mod;}return (*this);}constexpr mint& operator-=(const mint& rhs) noexcept {v += _mod - rhs.val();if (v >= _mod) {v -= _mod;}return (*this);}constexpr mint& operator*=(const mint& rhs) noexcept {v = (u64)v * rhs.val() % _mod;return (*this);}constexpr mint operator+(const mint& r) const noexcept {return mint(*this) += r;}constexpr mint operator-(const mint& r) const noexcept {return mint(*this) -= r;}constexpr mint operator*(const mint& r) const noexcept {return mint(*this) *= r;}constexpr mint& operator+=(i64 rhs) noexcept {(*this) += mint(rhs);return (*this);}constexpr mint& operator-=(i64 rhs) noexcept {(*this) -= mint(rhs);return (*this);}constexpr mint& operator*=(i64 rhs) noexcept {(*this) *= mint(rhs);return (*this);}constexpr friend mint operator+(i64 l, const mint& r) noexcept {return mint(l) += r;}constexpr friend mint operator-(i64 l, const mint& r) noexcept {return mint(l) -= r;}constexpr friend mint operator*(i64 l, const mint& r) noexcept {return mint(l) *= r;}constexpr mint operator+(i64 r) const noexcept { return mint(*this) += r; }constexpr mint operator-(i64 r) const noexcept { return mint(*this) -= r; }constexpr mint operator*(i64 r) const noexcept { return mint(*this) *= r; }constexpr mint& operator=(i64 r) noexcept { return (*this) = mint(r); }constexpr bool operator==(const mint& r) const noexcept {return (*this).val() == r.val();}template <typename T, internal::is_integral_t<T>* = nullptr>constexpr mint pow(T e) const noexcept {mint ans(1), base(*this);while (e) {if (e & 1) {ans *= base;}base *= base;e >>= 1;}return ans;}constexpr mint inv() const noexcept {long long x, y;auto d = ext_gcd((long long)_mod, (long long)v, x, y);assert(d == 1);return mint(y);}constexpr mint& operator/=(const mint& r) noexcept {return (*this) *= r.inv();}constexpr mint operator/(const mint& r) const noexcept {return mint(*this) *= r.inv();}constexpr friend mint operator/(const mint& l, i64 r) noexcept {return mint(l) /= mint(r);}constexpr friend mint operator/(i64 l, const mint& r) noexcept {return mint(l) /= mint(r);}};}; // namespace kyopro/*** @brief static modint*/#line 2 "Library/src/stream.hpp"#include <ctype.h>#include <stdio.h>#include <string>#line 6 "Library/src/stream.hpp"namespace kyopro {inline void single_read(char& c) {c = getchar_unlocked();while (isspace(c)) c = getchar_unlocked();}template <typename T, internal::is_integral_t<T>* = nullptr>inline void single_read(T& a) {a = 0;bool is_negative = false;char c = getchar_unlocked();while (isspace(c)) {c = getchar_unlocked();}if (c == '-') is_negative = true, c = getchar_unlocked();while (isdigit(c)) {a = 10 * a + (c - '0');c = getchar_unlocked();}if (is_negative) a *= -1;}template <typename T, internal::is_modint_t<T>* = nullptr>inline void single_read(T& a) {long long x;single_read(x);a = T(x);}inline void single_read(std::string& str) noexcept {char c = getchar_unlocked();while (isspace(c)) c = getchar_unlocked();while (!isspace(c)) {str += c;c = getchar_unlocked();}}template<typename T>inline void read(T& x) noexcept {single_read(x);}template <typename Head, typename... Tail>inline void read(Head& head, Tail&... tail) noexcept {single_read(head), read(tail...);}inline void single_write(char c) noexcept { putchar_unlocked(c); }template <typename T, internal::is_integral_t<T>* = nullptr>inline void single_write(T a) noexcept {if (!a) {putchar_unlocked('0');return;}if constexpr (std::is_signed_v<T>) {if (a < 0) putchar_unlocked('-'), a *= -1;}constexpr int d = std::numeric_limits<T>::digits10;char s[d + 1];int now = d + 1;while (a) {s[--now] = (char)'0' + a % 10;a /= 10;}while (now <= d) putchar_unlocked(s[now++]);}template <typename T, internal::is_modint_t<T>* = nullptr>inline void single_write(T a) noexcept {single_write(a.val());}inline void single_write(const std::string& str) noexcept {for (auto c : str) {putchar_unlocked(c);}}template <typename T> inline void write(T x) noexcept { single_write(x); }template <typename Head, typename... Tail>inline void write(Head head, Tail... tail) noexcept {single_write(head);putchar_unlocked(' ');write(tail...);}template <typename... Args> inline void put(Args... x) noexcept {write(x...);putchar_unlocked('\n');}}; // namespace kyopro/*** @brief 高速入出力*/#line 2 "Library/src/template.hpp"#include <bits/stdc++.h>#define rep(i, n) for (int i = 0; i < (n); i++)#define all(x) std::begin(x), std::end(x)#define popcount(x) __builtin_popcountll(x)using i128 = __int128_t;using ll = long long;using ld = long double;using graph = std::vector<std::vector<int>>;using P = std::pair<int, int>;constexpr int inf = std::numeric_limits<int>::max() / 2;constexpr ll infl = std::numeric_limits<ll>::max() / 2;const long double pi = acosl(-1);constexpr uint64_t MOD = 1e9 + 7;constexpr uint64_t MOD2 = 998244353;constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};template <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) {return a < b && (a = b, true);}template <typename T1, typename T2> constexpr inline bool chmin(T1& a, T2 b) {return a > b && (a = b, true);}#line 6 "a.cpp"using namespace std;using namespace kyopro;using mint = modint<998244353>;int main() {int n, m;read(n, m);auto res = rho::exp_factorize(m);mint ans = mint::raw(1);for (auto factor : res) {ans *= mint::raw(factor.second + 1).pow(n) -mint::raw(factor.second).pow(n);}put(ans);}