結果
問題 | No.2497 GCD of LCMs |
ユーザー |
![]() |
提出日時 | 2023-10-06 22:16:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 1,253 bytes |
コンパイル時間 | 4,337 ms |
コンパイル使用メモリ | 261,128 KB |
最終ジャッジ日時 | 2025-02-17 05:14:54 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 int main(){ int N,M; cin>>N>>M; set<int> S; vector<int> a(N); rep(i,N){ cin>>a[i]; int t = a[i]; for(int j=2;j*j<=t;j++){ if(t%j==0){ S.insert(j); while(t%j==0)t /= j; } } if(t>1)S.insert(t); } vector<mint> ans(N,1); vector<vector<int>> E(N); rep(i,M){ int u,v; cin>>u>>v; u--,v--; E[u].push_back(v); E[v].push_back(u); } for(auto x:S){ vector<int> c(N); rep(i,N){ while(a[i]%x==0){ c[i] ++; a[i] /= x; } } vector<int> dis(N,Inf32); dis[0] = c[0]; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> Q; Q.emplace(c[0],0); while(Q.size()>0){ int D = Q.top().first; int u = Q.top().second; Q.pop(); if(dis[u]!=D)continue; rep(i,E[u].size()){ int v = E[u][i]; int DD = max(D,c[v]); if(DD < dis[v]){ dis[v] = DD; Q.emplace(DD,v); } } } rep(i,N){ ans[i] *= mint(x).pow(dis[i]); } } rep(i,N){ cout<<ans[i].val()<<endl; } return 0; }