結果
問題 | No.2264 Gear Coloring |
ユーザー |
![]() |
提出日時 | 2023-04-07 23:01:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 3,863 bytes |
コンパイル時間 | 3,187 ms |
コンパイル使用メモリ | 258,708 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-02 20:19:57 |
合計ジャッジ時間 | 4,208 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>using namespace std;#define show(...) static_cast<void>(0)#define all(c) begin(c), end(c)#define for(...) for ([[maybe_unused]] auto&& __VA_ARGS__)#define lambda(...) [&](auto&&... args) { return __VA_ARGS__; }#define $1 get<0>(tie(args...))#define $2 get<1>(tie(args...))template <bool = false> struct Rep {int l, r, d;Rep begin() const;int end() const;bool operator!=(int) const;void operator++();int operator*() const;};Rep<> rep(int, int, int = 1);Rep<> rep1(int, int, int = 1);Rep<true> per(int, int, int = 1);Rep<true> per1(int, int, int = 1);template <class R> int len(R&&);template <class R, class I> int len(R&&, I);template <class T, class U = T> bool chmin(T&, U&&);template <class T, class U = T> bool chmax(T&, U&&);template <class T> ostream& operator<<(ostream&, const vector<T>&);template <class T> auto operator<<(ostream& os, T&& t) -> decltype(tuple_cat(t), os);template <class T = int> T input();template <class... Ts> void print(Ts&&...);using Fp = atcoder::modint998244353;vector<int> divisors(int n) {vector<int> ret;for (i = 1; i * i <= n; ++i) {if (n % i == 0) {ret.push_back(i);if (i * i < n) {ret.push_back(n / i);}}}sort(all(ret));return ret;}vector<int> go(int n, const vector<int>& d) {vector<int> ret(len(d));for (i : per(0, len(d))) {ret[i] = n / d[i];for (j : rep(i + 1, len(d))) {if (d[j] % d[i] == 0) {ret[i] -= ret[j];}}}return ret;}void solve() {int n = input();int m = input();vector<int> a(n);generate(all(a), input<>);int L = accumulate(all(a), 1, lcm<int, int>);auto d = divisors(L);auto f = go(L, d);Fp ans = 0;for (i : rep(0, len(d))) {Fp cur = 1;for (e : a) {cur *= Fp(m).pow(gcd(e, d[i]));}ans += cur * f[i];}ans /= L;print(ans.val());}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);solve();}template <bool R>Rep<R> Rep<R>::begin() const {return *this;}template <bool R>int Rep<R>::end() const {return 0;}template <bool R>bool Rep<R>::operator!=(int) const {return l <= r;}template <bool R>void Rep<R>::operator++() {if constexpr (R) {r -= d;} else {l += d;}}template <bool R>int Rep<R>::operator*() const {if constexpr (R) {return r;} else {return l;}}inline Rep<> rep(int l, int r, int d) {assert(0 < d);return {l, r - 1, d};}inline Rep<> rep1(int l, int r, int d) {assert(0 < d);return {l, r, d};}inline Rep<true> per(int l, int r, int d) {assert(0 < d);assert((r - l) % d == 0);return {l, r - d, d};}inline Rep<true> per1(int l, int r, int d) {assert(0 < d);return {l, r, d};}template <class R>int len(R&& r) {return static_cast<int>(size(forward<R>(r)));}template <class R, class I>int len(R&& r, I i) {return static_cast<int>(distance(begin(forward<R>(r)), i));}template <class T, class U>bool chmin(T& x, U&& y) {return y < x && (x = forward<U>(y), true);}template <class T, class U>bool chmax(T& x, U&& y) {return x < y && (x = forward<U>(y), true);}template <class T>ostream& operator<<(ostream& os, const vector<T>& v) {auto sep = "";for (e : v) {os << exchange(sep, " ") << e;}return os;}template <class T>auto operator<<(ostream& os, T&& t) -> decltype(tuple_cat(t), os) {auto f = [&](auto&&... args) -> ostream& {[[maybe_unused]] auto sep = "";(..., (os << exchange(sep, " ") << forward<decltype(args)>(args)));return os;};return apply(f, forward<T>(t));}template <class T>T input() {T x;cin >> x;return x;}template <class... Ts>void print(Ts&&... xs) {cout << forward_as_tuple(forward<Ts>(xs)...) << '\n';}