結果
問題 |
No.3250 最小公倍数
|
ユーザー |
![]() |
提出日時 | 2025-08-30 14:57:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,578 bytes |
コンパイル時間 | 5,642 ms |
コンパイル使用メモリ | 335,028 KB |
実行使用メモリ | 154,548 KB |
最終ジャッジ日時 | 2025-08-30 14:57:38 |
合計ジャッジ時間 | 27,121 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | WA * 18 TLE * 3 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; using mint = modint998244353; const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n) - 1; i >= 0; --i) #define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define P pair<int,int> template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } #include <vector> #include <algorithm> class Tree { public: Tree(int n, int root) : n(n), root(root) { edge.resize(n); for (int i = 0; i < MAXLOGV; i++) parent[i].resize(n); depth.resize(n); } // uとvをつなぐ // lcaを求めることが主目的なので無向グラフとしている void unite(int u, int v) { edge[u].push_back(v); edge[v].push_back(u); } // initする // コンストラクタだけじゃなくてこれも呼ばないとlcaが求められないぞ void init() { dfsOrder.resize(n); dfs(root, -1, 0); for (int k = 0; k + 1 < MAXLOGV; k++) { for (int v = 0; v < n; v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } // uとvのlcaを求める int lca(int u, int v) const { if (depth[u] > depth[v]) std::swap(u, v); for (int k = 0; k < MAXLOGV; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = MAXLOGV - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } // uのn個親を求める int pare(int v, int n) { if (depth[v] < n)return -1; n = std::min(n, depth[v]); int idx = MAXLOGV; while (n) { for (int i = idx - 1; i >= 0; --i) { if (n < (1 << i))continue; if (-1 == parent[i][v])continue; n -= (1 << i); v = parent[i][v]; idx = i; break; } } return v; } // uからvに向かってd進んだ頂点を返す int JumpOnTree(int u, int v, int d) { if (0 == d)return u; int distuv = dist(u, v); if (distuv < d)return -1; int l = lca(u, v); if (l == u)return pare(v, distuv - d); if (l == v)return pare(u, d); int distlu = dist(l, u); if (distlu >= d)return pare(u, d); return pare(v, distuv - d); } // uとvの距離を求める // edgeを定義しないといけない時はこれじゃダメ int dist(int u, int v) const { int p = lca(u, v); return (depth[u] - depth[p]) + (depth[v] - depth[p]); } //頂点wが頂点u,vのパス上に存在するか bool on_path(int u, int v, int w) { return (dist(u, w) + dist(v, w) == dist(u, v)); } int tmp = 0; int dfs(int v, int p, int d) { dfsOrder[v] = tmp; tmp++; int ret = 1; parent[0][v] = p; depth[v] = d; for (int next : edge[v]) { if (next == p) continue; auto get = dfs(next, v, d + 1); ret += get; } return ret; } static const int MAXLOGV = 25; // グラフの隣接リスト表現 std::vector<std::vector<int>>edge; // 頂点の数 int n; // 根ノードの番号 int root; // 親ノード std::vector<int> parent[MAXLOGV]; // 根からの深さ std::vector<int> depth; // dfsorder std::vector<int>dfsOrder; }; class Osa_k { public: Osa_k(int max = 1000006) { osa_k.resize(max + 1); } void init() { osa_k[1] = 1; for (int i = 2; i < osa_k.size(); ++i) { if (0 != osa_k[i])continue; osa_k[i] = i; for (int j = i * 2; j < osa_k.size(); j += i) { if (0 == osa_k[j]) osa_k[j] = i; } } } std::vector<int> osk(int n) { std::vector<int>result; while (1 != n) { result.push_back(osa_k[n]); n /= osa_k[n]; } return result; } std::vector<std::pair<int, int>>oskPair(int n) { auto ps = osk(n); std::vector<std::pair<int, int>> result; for (int i = 0; i < ps.size();) { int j = i + 1; while (j < ps.size() && ps[i] == ps[j])j++; result.emplace_back(ps[i], j - i); i = j; } return result; } private: std::vector<int>osa_k; }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; cin >> n; vector<int>a(n); rep(i, n)cin >> a[i]; vector to(n, vector<int>()); Tree tr(n, 0); rep(i, n - 1) { int u, v; cin >> u >> v; u--, v--; to[u].push_back(v); to[v].push_back(u); tr.unite(u, v); } tr.init(); vector<int>order(n); iota(all(order), 0); std::sort(order.begin(), order.end(), [&](int l, int r) { return tr.dfsOrder[l] < tr.dfsOrder[r]; } ); Osa_k osak; osak.init(); vector ps(1e6, vector<int>()); for (auto e : order) { for (auto[p, q] : osak.oskPair(a[e])) { ps[p].push_back(e); } } vector<mint>ans(n); rep(i, n)ans[i] = a[i]; rep(p, ps.size()) { if (ps[p].empty())continue; mint ip = mint(p).inv(); auto ids = ps[p]; while (!ids.empty()) { int sz = ids.size(); rep(i, sz - 1) { int j = i + 1; ans[tr.lca(ids[i], ids[j])] *= ip; } vector<int>nids; rep(i, sz) { int v = ids[i]; a[v] /= p; if (a[v] % p)continue; nids.push_back(v); } ids.swap(nids); break; } } rrep(i, n) { int v = order[i]; for (auto u : to[v])if (tr.dfsOrder[u] < tr.dfsOrder[v]) { ans[u] *= ans[v]; } } for (auto e : ans)cout << e.val() << endl; return 0; }