結果

問題 No.2497 GCD of LCMs
ユーザー 00 Sakuda00 Sakuda
提出日時 2024-04-11 13:08:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 42 ms / 2,000 ms
コード長 9,421 bytes
コンパイル時間 3,291 ms
コンパイル使用メモリ 249,484 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-02 21:33:50
合計ジャッジ時間 4,298 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 10 ms
5,248 KB
testcase_08 AC 18 ms
5,248 KB
testcase_09 AC 20 ms
5,248 KB
testcase_10 AC 31 ms
5,248 KB
testcase_11 AC 16 ms
5,248 KB
testcase_12 AC 34 ms
5,248 KB
testcase_13 AC 40 ms
5,248 KB
testcase_14 AC 19 ms
5,248 KB
testcase_15 AC 21 ms
5,248 KB
testcase_16 AC 42 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <iomanip>
using namespace std;
using ll = long long;
using VVI = vector<vector<int>>;
using VVL = vector<vector<ll>>;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
using VC = vector<char>;
using VP = vector<pair<int, int>>;
using Graph0 = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define drep(i, a, b) for (int i = (int)(a);i >= (int)(b);i--)
#define urep(i, a, b) for (int i = (int)(a);i <= (int)(b);i++)
#define lrep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ldrep(i, a, b) for (ll i = (ll)(a);i >= (ll)(b);i--)
#define lurep(i, a, b) for (ll i = (ll)(a);i <= (ll)(b);i++)
#define arep(i, v) for (auto i : v)
#define all(a) (a).begin(), (a).end()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define eyes cout << "Yes" << endl;exit(0);
#define eno cout << "No" << endl;exit(0);
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b; 
    return true;
  }
  return false;
}
template<typename T>
void excout(T A) {
  cout << A << endl;
  exit(0);
}
constexpr long long INF = (1LL << 60); // INFにちゅういい！

// 辺の情報
struct Edge
{
  // 行先
  int to;

  // コスト
  int cost;
};

using Graph = std::vector<std::vector<Edge>>;

// { distance, from }
using Pair = std::pair<long long, int>;

// ダイクストラ法 (1.1 基本実装)
// distances は頂点数と同じサイズ, 全要素 INF で初期化しておく
void Dijkstra(const Graph& graph, std::vector<long long>& distances, int startIndex)
{
  // 「現時点での最短距離, 頂点」の順に取り出す priority_queue
  // デフォルトの priority_queue は降順に取り出すため std::greater を使う
  std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> q;
  q.emplace((distances[startIndex] = 0), startIndex);

  while (!q.empty())
  {
    const long long distance = q.top().first;
    const int from = q.top().second;
    q.pop();

    // 最短距離でなければ処理しない
    if (distances[from] < distance)
    {
      continue;
    }

    // 現在の頂点からの各辺について
    for (const auto& edge : graph[from])
    {
      // to までの新しい距離
      const long long d = (distances[from] + edge.cost);

      // d が現在の記録より小さければ更新
      if (d < distances[edge.to])
      {
        q.emplace((distances[edge.to] = d), edge.to);
      }
    }
  }
}
template<typename T>
T MODS(T a, T mods) {
  return ((((((a + mods) % mods) + mods) % mods)));
}
//combination 列挙用 --int ver
VVI comb(int n, int r) {
  VVI v(n + 1, VI (n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}
vector<pair<long long, long long> > prime_factorize(long long N) {
    // 答えを表す可変長配列
    vector<pair<long long, long long> > res;

    // √N まで試し割っていく
    for (long long p = 2; p * p <= N; ++p) {
        // N が p で割り切れないならばスキップ
        if (N % p != 0) {
            continue;
        }

        // N の素因数 p に対する指数を求める
        int e = 0;
        while (N % p == 0) {
            // 指数を 1 増やす
            ++e;

            // N を p で割る
            N /= p;
        }

        // 答えに追加
        res.emplace_back(p, e);
    }

    // 素数が最後に残ることがありうる
    if (N != 1) {
        res.emplace_back(N, 1);
    }
    return res;
}
using UNION_TYPE = int;
struct UnionFind {
    vector<UNION_TYPE> par, siz;
    UnionFind(UNION_TYPE n) : par(n, -1), siz(n, 1) {}
    UNION_TYPE root(UNION_TYPE x) {
        if (par[x] == -1) return x;
        else return par[x] = root(par[x]);
    }
    bool issame(UNION_TYPE x, UNION_TYPE y) {
        return root(x) == root(y);
    }
    bool unite(UNION_TYPE x, UNION_TYPE y) {
        x = root(x);y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        par[y] = x;
        siz[x] += siz[y];
        return true;
    }
    UNION_TYPE size(UNION_TYPE x) {
        return siz[root(x)];
    }
};
//mod func の型に注意！！！
//Union Find はUNION_TYPE で型変可能！
//
VI topo_sort(Graph0& G) {
  int N = G.size();
  VI IND(N, 0);
  rep(v, N) {
    arep(nv, G[v]) {
      IND[nv]++;
    }
  }
  queue<int> que;
  rep(v, N) {
    if (IND[v] == 0) {
      que.push(v);
    }
  }
  VI ANS;
  while (!que.empty()) {
    int v = que.front();
    ANS.push_back(v);
    que.pop();
    arep(nv, G[v]) {
      IND[nv]--;
      if (IND[nv] == 0) {
        que.push(nv);
      }
    }
  }
  return ANS;
}
void ADD(int a, int b, Graph0& G) {
  G[a].push_back(b);
  G[b].push_back(a);
}
VP near(int i, int j, int H, int W) {
  VP ans;
  VP cand = {{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}};
  arep(v, cand) {
    if (v.first < 0 or v.first >= H) continue;
    if (v.second < 0 or v.second >= W) continue;
    ans.push_back(v);
  }
  return ans;
}
int cast(int i, int j, int H, int W) {
  return ((W * i) + j);
}
ll pows(ll x, ll n, ll mod) {
    if (!n) return 1;
    x %= mod;
    ll r = pows(x, n / 2, mod);
    (r *= r) %= mod;
    if (n % 2) (r *=x) %= mod;
    return r;
}
struct COMB_MOD {
  ll mod;
  int MAX;
  VL fac, finv, inv;
  COMB_MOD(int max, ll m) {
    fac.assign(max, 0);
    finv.assign(max, 0);
    inv.assign(max, 0);
    mod = m;
    MAX = max;
  }
  void solve() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;

        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
    
  }
  ll comb(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
  }
};

struct LCA {
    vector<vector<int>> parent;  // parent[k][u]:= u の 2^k 先の親
    vector<int> dist;            // root からの距離
    LCA(const Graph0 &G, int root = 0) { init(G, root); }

    // 初期化
    void init(const Graph0 &G, int root = 0) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++;
        parent.assign(K, vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                } else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    // 根からの距離と1つ先の頂点を求める
    void dfs(const Graph0 &G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e != p) dfs(G, e, v, d + 1);
        }
    }

    int query(int u, int v) {
        if (dist[u] < dist[v]) swap(u, v);  // u の方が深いとする
        int K = parent.size();
        // LCA までの距離を同じにする
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        // 二分探索で LCA を求める
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
    int get_dist(int u, int v) { return dist[u] + dist[v] - 2 * dist[query(u, v)]; }
};
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
int main(void) {
  int N, M;cin >> N >> M;
  VL A(N);
  Graph0 G(N);
  rep(i, N) cin >> A[i];
  rep(i, M) {
    int u, v;cin >> u >> v;
    u--;v--;
    ADD(u, v, G);
  }
  vector<vector<pair<ll, ll>>> PR(N);
  set<ll> PS;
  rep(i, N) {
    auto res = prime_factorize(A[i]);
    PR[i] = res;
    arep(v, res) PS.insert(v.first);
  }
  VI ps;
  int K = 0;
  map<ll, int> tos;
  arep(v, PS) {
    tos[v] = K;
    ps.push_back(v);
    K++;
  }
  vector<mint> ans(N, 1);
  rep(i, K) {
    VVI ORD(60);
    VI B(N, 0);
    rep(v, N) {
      int ord = 0;
    arep(pr, PR[v]) {
      if (pr.first == ps[i]) {
        ord = pr.second;
      }
    }
    ORD[ord].push_back(v);
    B[v] = ord;
    }
    UnionFind uf(N);
    int ord = 0;
    vector<bool> IS(N, false);
    rep(k, 60) {
      arep(v,ORD[k]) {
       // cout << k << " " << ps[i] << " " << v+ 1 << endl;
        arep(nv, G[v]) {
          if (B[nv] <= k) {
            //cout << ps[i] << " " << v + 1 << " " << nv + 1 << " " << k << endl;
            uf.unite(v, nv);
          }
        }
      }
      rep(nv, N) {
        if (IS[nv]) continue;
        if (uf.issame(0, nv)) {
          IS[nv] = true;
          ans[nv] *= mint(ps[i]).pow(k);
        }
      }
    } 
  }
  ans[0] = A[0];
  rep(v, N) cout << ans[v].val() << endl;
}
0