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

提出ソース
結果

問題	No.3250 最小公倍数
ユーザー	kwm_t
提出日時	2025-08-30 15:14:10
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,152 ms / 2,000 ms
コード長	7,930 bytes
コンパイル時間	6,101 ms
コンパイル使用メモリ	334,352 KB
実行使用メモリ	222,116 KB
最終ジャッジ日時	2025-08-30 15:14:33
合計ジャッジ時間	18,367 ms
ジャッジサーバーID （参考情報）	judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 21
権限があれば一括ダウンロードができます
ソースコード

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) : 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;
};

/*pair<vector<int>, vector<int>> primes_lpf(const int n) {
	vector<int> primes; primes.reserve(n / 10);
	vector<int> lpf(n + 1);
	for (int i = 2; i <= n; i += 2) lpf[i] = 2;
	for (int i = 3; i <= n; i += 6) lpf[i] = 3;
	if (2 <= n) primes.push_back(2);
	if (3 <= n) primes.push_back(3);
	// 5 * x <= n, x <= floor(n / 5)
	const int n5 = n / 5;
	int x = 5;
	char add_next = 2;
	for (; x <= n5; x += add_next, add_next ^= 0x2 ^ 4) {
		int px = lpf[x];
		if (px == 0) {
			lpf[x] = px = x;
			primes.push_back(x);
		}
		for (int i = 2;; ++i) {
			int q = primes[i];
			int y = q * x;
			if (y > n) break;
			lpf[y] = q;
			if (q == px) break;
		}
	}
	for (; x <= n; x += add_next, add_next ^= 0x2 ^ 4) {
		if (lpf[x] == 0) {
			lpf[x] = x;
			primes.push_back(x);
		}
	}
	return { move(primes), move(lpf) };
}

constexpr int PSIZE = 1000000;
auto[primes, lpf] = primes_lpf(PSIZE);

vector<pair<int, int>>& factorize_lv(int x) {
	int ps[10], cs[10];
	int sz = 0;
	while (x != 1) {
		int p = lpf[x], c = 0;
		do { x /= p; c++; } while (x % p == 0);
		ps[sz] = p; cs[sz] = c; sz++;
	}
	static vector<pair<int, int>> fs;
	fs.clear();
	for (int i = 0; i < sz; i++) fs.emplace_back(ps[i], cs[i]);
	return fs;
}*/

struct LCA {
	int n;
	vector<int> idx;
	struct S { int v, 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;
	}
};


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);
	}
	LCA lca(to, 0);
	//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];
		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);
		}
	}

	/*for (int v : order) {
		for (auto[p, e] : factorize_lv(a[v])) {
			ps[p].emplace_back(v);
		}
	}*/

	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 = 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];
				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;
}
yukicoder

結果

ソースコード
