#1116345 (C++23) No.3250 最小公倍数

提出ソース
結果

問題	No.3250 最小公倍数
コンテスト
ユーザー	kwm_t
提出日時	2025-08-30 15:56:50
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,019 ms / 2,000 ms
コード長	6,893 bytes
コンパイル時間	6,504 ms
コンパイル使用メモリ	334,272 KB
実行使用メモリ	249,988 KB
最終ジャッジ日時	2025-11-09 23:16:29
合計ジャッジ時間	17,113 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 23
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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 = 0) : n(n), root(root) {
		edge.resize(n);
		for (int i = 0; i < MAXLOGV; i++) parent[i].resize(n);
		depth.resize(n);
		in.resize(n);
		out.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() {
		auto dfs = [&](auto &&self, int &time, int v, int p, int d)->void {
			in[v] = time;
			time++;

			parent[0][v] = p;
			depth[v] = d;
			for (int nv : edge[v]) {
				if (nv == p) continue;
				self(self, time, nv, v, d + 1);
			}
			out[v] = time;
		};
		int time = 0;
		dfs(dfs, time, 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));
	}
	static const int MAXLOGV = 25;
	// グラフの隣接リスト表現
	std::vector<std::vector<int>>edge;
	// 頂点の数
	int n;
	// 根ノードの番号
	int root;
	// 親ノード
	std::vector<int> parent[MAXLOGV];
	// 根からの深さ
	std::vector<int> depth;
	// eulerTour
	std::vector<int> in, out;
};*/
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;
};
struct LCA {
	int n;
	vector<int> idx;
	struct S {
		int v, depth;
		S() {}
		constexpr S(int v, int depth) : v(v), depth(depth) {}
	};
	vector<vector<S>> spt;
	static constexpr S min(S x, S y) { return x.depth < y.depth ? x : y; }
	LCA(const std::vector<std::vector<int>>& g, int root) : n(g.size()), idx(n, -1) {
		assert(0 <= root && root < n);
		vector<S> tour;
		auto dfs = [&](auto&& self, int u, int d) -> void {
			idx[u] = tour.size();
			tour.emplace_back(u, d);
			for (int v : g[u]) if (idx[v] == -1) {
				self(self, v, d + 1);
				tour.emplace_back(u, d);
			}
		};
		dfs(dfs, root, 0);
		int m = tour.size();
		int w = bit_width(m + 0U);
		spt.resize(w);
		spt[0] = move(tour);
		for (int k = 0; k + 1 < w; k++) {
			int k2 = 1 << k;
			int sz = m - 2 * k2 + 1;
			spt[k + 1].resize(sz);
			for (int i = 0; i < sz; i++) spt[k + 1][i] = min(spt[k][i], spt[k][i + k2]);
		}
	}
	int lca(int u, int v) {
		int l = idx[u], r = idx[v];
		if (l > r) swap(l, r);
		int k = bit_width(r - l + 1U) - 1;
		return min(spt[k][l], spt[k][r + 1 - (1 << k)]).v;
	}
	static int bit_width(unsigned int x) noexcept {
#ifdef _MSC_VER
		if (x == 0) return 0;
		unsigned long index;
		_BitScanReverse(&index, x);
		return static_cast<int>(index) + 1;
#else
		return std::bit_width(x); // C++20～
#endif
	}
};
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>());
	rep(i, n - 1) {
		int u, v; cin >> u >> v;
		u--, v--;
		to[u].push_back(v);
		to[v].push_back(u);
	}
	LCA lca(to, 0);
	vector<int>order(n);
	iota(all(order), 0);
	std::sort(order.begin(), order.end(), [&](int l, int r) {
		return lca.idx[l] < lca.idx[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, 1);
	rep(p, ps.size()) {
		if (ps[p].empty())continue;
		mint ip = mint(p).inv();
		auto ids = move(ps[p]);
		while (!ids.empty()) {
			int sz = ids.size();
			rep(i, sz - 1) {
				int j = i + 1;
				ans[lca.lca(ids[i], ids[j])] *= ip;
			}
			int nsz = 0;
			rep(i, sz) {
				int v = ids[i];
				ans[v] *= p;
				a[v] /= p;
				if (a[v] % p)continue;
				ids[nsz++] = v;
			}
			ids.resize(nsz);
		}
	}
	rrep(i, n) {
		int v = order[i];
		for (auto u : to[v])if (lca.idx[u] < lca.idx[v]) {
			ans[u] *= ans[v];
		}
	}
	for (auto e : ans)cout << e.val() << '\n';
	return 0;
}// lcaが遅いらしい
yukicoder

結果

ソースコード
