結果
問題 |
No.2497 GCD of LCMs
|
ユーザー |
![]() |
提出日時 | 2023-10-06 21:41:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 369 ms / 2,000 ms |
コード長 | 1,864 bytes |
コンパイル時間 | 2,263 ms |
コンパイル使用メモリ | 213,632 KB |
最終ジャッジ日時 | 2025-02-17 04:56:18 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; int main(){ int N, M; cin >> N >> M; vector<int> A(N); for (int i = 0; i < N; i++){ cin >> A[i]; } vector<vector<int>> E(N); for (int i = 0; i < M; i++){ int U, V; cin >> U >> V; U--; V--; E[U].push_back(V); E[V].push_back(U); } vector<vector<pair<int, int>>> F(N); for (int i = 0; i < N; i++){ for (int j = 2; j * j <= A[i]; j++){ if (A[i] % j == 0){ int cnt = 0; while (A[i] % j == 0){ A[i] /= j; cnt++; } F[i].push_back(make_pair(j, cnt)); } } if (A[i] > 1){ F[i].push_back(make_pair(A[i], 1)); } } vector<int> P; for (int i = 0; i < N; i++){ for (pair<int, int> pe : F[i]){ P.push_back(pe.first); } } sort(P.begin(), P.end()); P.erase(unique(P.begin(), P.end()), P.end()); int cnt = P.size(); vector<vector<int>> e(N, vector<int>(cnt, 0)); for (int i = 0; i < N; i++){ for (pair<int, int> pe : F[i]){ int idx = lower_bound(P.begin(), P.end(), pe.first) - P.begin(); e[i][idx] = pe.second; } } vector<long long> ans(N, 1); for (int i = 0; i < cnt; i++){ vector<int> d(N, -1); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push(make_pair(e[0][i], 0)); while (!pq.empty()){ int c = pq.top().first; int v = pq.top().second; pq.pop(); if (d[v] == -1){ d[v] = c; for (int w : E[v]){ if (d[w] == -1){ pq.push(make_pair(max(c, e[w][i]), w)); } } } } for (int j = 0; j < N; j++){ for (int k = 0; k < d[j]; k++){ ans[j] *= P[i]; ans[j] %= MOD; } } } for (int i = 0; i < N; i++){ cout << ans[i] << endl; } }