結果
問題 | No.2497 GCD of LCMs |
ユーザー |
|
提出日時 | 2023-10-06 22:30:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 28 ms / 2,000 ms |
コード長 | 2,547 bytes |
コンパイル時間 | 3,686 ms |
コンパイル使用メモリ | 267,916 KB |
最終ジャッジ日時 | 2025-02-17 05:18:38 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;//only for atcoder#include<atcoder/all>using namespace atcoder;#define rep(i,l,r) for(ll i=(l); i<(r); i++)#define rrep(i,l,r) for(ll i=(r)-1; i>=(l); i--)#define ALL(c) (c).begin(), (c).end()#define RALL(c) (c).rbegin(), (c).rend()#define REV(c) reverse(ALL(c))#define SORT(c) sort(ALL(c))#define RSORT(c) sort(RALL(c))#define MINV(c) *min_element(ALL(c))#define MAXV(c) *max_element(ALL(c))template <typename TYPE>void print(TYPE vec){rep(i,0,vec.size()){cout << vec[i];if(i == vec.size()-1){cout << endl;}else{cout << " ";}}}using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;using VS = vector<string>;using VVS = vector<VS>;using VB = vector<bool>;using VVB = vector<VB>;using VC = vector<char>;using VVC = vector<VC>;using VD = vector<ld>;using VVD = vector<VD>;using P = pair<ll,ll>;using VP = vector<P>;using VVP = vector<VP>;const ll LINF = 2e18;const int INF = 2e9;using mint = modint998244353;//素因数分解(関数ver)改map<long long,long long> prime_fact(long long n){long long a = 2;map<long long,long long> mp;while(n >= a*a){if(n %a == 0){mp[a]++;n /= a;}else{a++;}}if(n != 1){mp[n]++;}return mp;}int main(){int N, M;cin >> N >> M;VI vec(N);rep(i,0,N){cin >> vec[i];}set<int> S;rep(i,0,N){map<ll,ll> mp = prime_fact(vec[i]);for(auto itr = mp.begin(); itr != mp.end(); itr++){S.insert(itr->first);}}VVI G(N,VI(0));rep(i,0,M){int a, b;cin >> a >> b;a--; b--;G[a].push_back(b);G[b].push_back(a);}vector<mint> ans(N,1);for(auto itr = S.begin(); itr != S.end(); itr++){int x = (*itr);VI cnt(N);rep(i,0,N){int y = vec[i];while(y % x == 0){cnt[i]++;y /= x;}}priority_queue<P, vector<P>, greater<P>> PQ;PQ.push(P(cnt[0], 0));VI dp(N,INF);dp[0] = cnt[0];while(PQ.size()){auto[c, p] = PQ.top();PQ.pop();for(auto e : G[p]){if(dp[e] > max(dp[p], cnt[e])){dp[e] = max(dp[p] , cnt[e]);PQ.push(P(dp[e], e));}}}mint t = x;rep(i,0,N){ans[i] *= t.pow(dp[i]);}//cout << x << endl;//print<VI>(dp);}rep(i,0,N){cout << ans[i].val() << endl;}}