結果
| 問題 | No.2264 Gear Coloring |
| ユーザー |
 🍮かんプリン
|
| 提出日時 | 2023-04-08 23:21:51 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 64 ms / 2,000 ms |
| コード長 | 6,187 bytes |
| コンパイル時間 | 1,954 ms |
| コンパイル使用メモリ | 182,132 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-03 20:44:15 |
| 合計ジャッジ時間 | 2,999 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 18 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:214:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
214 | for (auto [p,e] : v) {
| ^
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2023.04.08 23:21:45**/#include "bits/stdc++.h"using namespace std;typedef long long ll;template< int MOD >struct mint {public:unsigned int x;mint() : x(0) {}mint(long long v) {long long w = (long long)(v % (long long)(MOD));if (w < 0) w += MOD;x = (unsigned int)(w);}mint(std::string &s) {unsigned int z = 0;for (int i = 0; i < s.size(); i++) {z *= 10;z += s[i] - '0';z %= MOD;}x = z;}mint operator+() const { return *this; }mint operator-() const { return mint() - *this; }mint& operator+=(const mint &a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}mint& operator-=(const mint &a) {if ((x -= a.x) >= MOD) x += MOD;return *this;}mint& operator*=(const mint &a) {unsigned long long z = x;z *= a.x;x = (unsigned int)(z % MOD);return *this;}mint& operator/=(const mint &a) {return *this = *this * a.inv(); }friend mint operator+(const mint& lhs, const mint& rhs) {return mint(lhs) += rhs;}friend mint operator-(const mint& lhs, const mint& rhs) {return mint(lhs) -= rhs;}friend mint operator*(const mint& lhs, const mint& rhs) {return mint(lhs) *= rhs;}friend mint operator/(const mint& lhs, const mint& rhs) {return mint(lhs) /= rhs;}friend bool operator==(const mint& lhs, const mint& rhs) {return lhs.x == rhs.x;}friend bool operator!=(const mint& lhs, const mint& rhs) {return lhs.x != rhs.x;}friend std::ostream& operator<<(std::ostream &os, const mint &n) {return os << n.x;}friend std::istream &operator>>(std::istream &is, mint &n) {unsigned int x;is >> x;n = mint(x);return is;}mint inv() const {assert(x);return pow(MOD-2);}mint pow(long long n) const {assert(0 <= n);mint p = *this, r = 1;while (n) {if (n & 1) r *= p;p *= p;n >>= 1;}return r;}mint sqrt() const {if (this->x < 2) return *this;if (this->pow((MOD-1)>>1).x != 1) return mint(0);mint b = 1, one = 1;while (b.pow((MOD-1) >> 1) == 1) b += one;long long m = MOD-1, e = 0;while (m % 2 == 0) m >>= 1, e += 1;mint x = this->pow((m - 1) >> 1);mint y = (*this) * x * x;x *= (*this);mint z = b.pow(m);while (y.x != 1) {int j = 0;mint t = y;while (t != one) j += 1, t *= t;z = z.pow(1LL << (e-j-1));x *= z; z *= z; y *= z; e = j;}return x;}};constexpr int MOD = 998244353;bool isprime(long long N) {if (N <= 1) return false;if (N == 2) return true;if (N % 2 == 0) return false;auto modpow = [](__int128_t a, long long n, long long mo) {__int128_t r = 1;a %= mo;while (n) r = r * ((n % 2) ? a : 1) % mo, a = a * a % mo, n >>= 1;return r;};std::vector<long long> A = {2, 325, 9375, 28178, 450775,9780504, 1795265022};long long s = 0, d = N - 1;while (d % 2 == 0) d >>= 1, s++;for (long long a : A) {if (a % N == 0) return true;long long j, r = modpow(a, d, N);if (r == 1) continue;for (j = 0; j < s; j++) {if (r == N - 1) break;r = __int128_t(r) * r % N;}if (j == s) return false;}return true;}long long PollardRho(long long N) {if (N % 2 == 0) return 2;long long m = 1LL<<(70-__builtin_clrsbll(N))/8;for (long long c = 1; c < N; c++) {auto f = [&](long long x) { return ((__int128_t)x*x+c)%N; };long long x,y,g,q,r,k,ys;y = k = 0;g = q = r = 1;while (g == 1) {x = y;while(k < 3*r/4) {y = f(y);k += 1;}while(k < r && g == 1) {ys = y;for (int _ = 0; _ < min(m,r-k); _++) {y = f(y);q = (__int128_t)q*abs(x-y)%N;}g = __gcd(q,N);k += m;}k = r;r <<= 1;}if (g == N) {g = 1;y = ys;while(g == 1) {y = f(y);g = __gcd(abs(x-y),N);}}if (g == N) continue;if (isprime(g)) return g;else if (isprime(N/g)) return N/g;else return PollardRho(g);}return -1;}vector<pair<long long,int>> prime_factorization(long long N) {vector<pair<long long,int>> res;while(!isprime(N) && N > 1) {long long p = PollardRho(N);int cnt = 0;while(N%p==0) {N /= p;cnt++;}res.push_back({p,cnt});}if (N > 1) res.push_back({N,1});sort(res.begin(), res.end());return res;}int main() {int n,m;cin >> n >> m;vector<int> a(n);int L = 1;for (int i = 0; i < n; i++) {cin >> a[i];L = (ll)L * a[i] / __gcd(a[i],L);}auto v = prime_factorization(L);vector<int> divisor,euler;divisor.push_back(1);euler.push_back(1);for (auto [p,e] : v) {int sz = divisor.size();for (int i = 0; i < e; i++) {for (int j = sz*i; j < sz*(i+1); j++) {divisor.push_back(divisor[j]*p);euler.push_back(euler[j]*(p-!i));}}}mint<MOD> ans = 0;for (int i = 0; i < euler.size(); i++) {int d = L/divisor[i];ll total = 0;for (int j = 0; j < n; j++) {total += __gcd(d,a[j]);}ans += mint<MOD>(m).pow(total)*euler[i];}cout << ans/L << endl;return 0;}