結果
| 問題 |
No.3250 最小公倍数
|
| コンテスト | |
| ユーザー |
👑  potato167
|
| 提出日時 | 2025-08-29 23:25:09 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,553 ms / 2,000 ms |
| コード長 | 17,006 bytes |
| コンパイル時間 | 2,687 ms |
| コンパイル使用メモリ | 230,372 KB |
| 実行使用メモリ | 187,420 KB |
| 最終ジャッジ日時 | 2025-11-09 23:10:38 |
| 合計ジャッジ時間 | 26,940 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 23 |
ソースコード
//#include <bits/stdc++.h>
//using namespace std;
//using ll=long long;
//const ll ILL=2167167167167167167;
//const int INF=2100000000;
//#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
//#define all(p) p.begin(),p.end()
//template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
//template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
//template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
//template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
//template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
//template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
//template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
//bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
//template<class T> void vec_out(vector<T> &p,int ty=0){
// if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
// else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
//template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
//template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
//template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
//int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;}
//template<class T> T square(T a){return a * a;}
//
//#include <atcoder/modint>
//
//std::vector<std::vector<int>> tree_in(int N){
// std::vector<std::vector<int>> G(N);
// for(int i=0;i<N-1;i++){
// int a;int b;
// cin>>a>>b;
// a--,b--;
// G[a].push_back(b);
// G[b].push_back(a);
// }
// return G;
//}
//std::tuple<std::vector<int>,std::vector<int>,std::vector<int>> tree_order_pare_depth(std::vector<std::vector<int>> &G,int root=0){
// int n=G.size();
// std::vector<int> order={root},pare(n,-1),depth(n);
// pare[root]=-2;
// for(int i=0;i<n;i++){
// int a=order[i];
// for(auto x:G[a]){
// if(pare[x]==-1){
// pare[x]=a;
// depth[x]=depth[a]+1;
// order.push_back(x);
// }
// }
// }
// return {order,pare,depth};
//}
//std::vector<int> tree_diameter_path(std::vector<std::vector<int>> &G){
// int n=G.size();
// auto r=(std::get<0>(tree_order_pare_depth(G,0))).at(n-1);
// std::vector<int> order,pare,depth,ans;
// tie(order,pare,depth)=tree_order_pare_depth(G,r);
// int ind=order[n-1];
// while(ind!=-2){
// ans.push_back(ind);
// ind=pare[ind];
// }
// return ans;
//}
//
////in[i] -> p[i]
////out[i] -> p[i+N]
//std::vector<int> Euler_Tour(std::vector<std::vector<int>> &G,int root){
// std::stack<int> s;
// int n=G.size();
// std::vector<int> p(n*2),seen(n);
// s.push(root);
// seen[root]=1;
// for(int i=0;i<2*n;i++){
// int a=s.top();
// p[a]=i;
// s.pop();
// if(a<n){
// s.push(a+n);
// for(auto x:G[a]){
// if(seen[x]==0){
// s.push(x);
// seen[x]=1;
// }
// }
// }
// }
// return p;
//}
//
//#include "po167_library/math/Binomial.hpp"
//#include "po167_library/graph/tree/LCA.hpp"
//using mint = atcoder::modint998244353;
//
//void solve();
//// POP'N ROLL MUSIC / TOMOO
//int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
//
// int t = 1;
// // cin >> t;
// rep(i, 0, t) solve();
//}
//
//void solve(){
// int N;
// cin >> N;
// vector<int> A(N);
// rep(i, 0, N) cin >> A[i];
// const int L = 1'000'100;
// vector<vector<int>> table(L);
// rep(i, 2, L) if (table[i].empty()){
// for (int j = i; j < L; j += i){
// int tmp = j;
// int c = 1;
// while (tmp % i == 0){
// tmp /= i;
// c *= i;
// table[j].push_back(c);
// }
// }
// }
// auto G = tree_in(N);
// auto E = Euler_Tour(G, 0);
// vector<int> order(N);
// rep(i, 0, N) order[i] = i;
// sort(all(order), [&](int l, int r){
// return E[l] < E[r];
// });
// po167::LCA lc(G);
// vector<int> la(L, -1);
// po167::Binomial<mint> Bi;
// vector<mint> ans(N, 1);
// for (auto var : order){
// ans[var] *= A[var];
// int a = -1, b = -1;
// for (auto x : table[A[var]]){
// if (la[x] != -1){
// if (a != la[x]) a = la[x], b = lc.lca(a, var);
// ans[b] *= Bi.inv(table[x].front());
// }
// la[x] = var;
// }
// }
// vector<int> pare, depth;
// tie(order, pare, depth) = tree_order_pare_depth(G, 0);
// reverse(all(order));
// rep(i, 0 ,N - 1){
// int a = order[i];
// ans[pare[a]] *= ans[a];
// }
// for (auto x : ans) cout << x.val() << "\n";
//}
//
#line 1 "a.cpp"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;}
template<class T> T square(T a){return a * a;}
#include <atcoder/modint>
std::vector<std::vector<int>> tree_in(int N){
std::vector<std::vector<int>> G(N);
for(int i=0;i<N-1;i++){
int a;int b;
cin>>a>>b;
a--,b--;
G[a].push_back(b);
G[b].push_back(a);
}
return G;
}
std::tuple<std::vector<int>,std::vector<int>,std::vector<int>> tree_order_pare_depth(std::vector<std::vector<int>> &G,int root=0){
int n=G.size();
std::vector<int> order={root},pare(n,-1),depth(n);
pare[root]=-2;
for(int i=0;i<n;i++){
int a=order[i];
for(auto x:G[a]){
if(pare[x]==-1){
pare[x]=a;
depth[x]=depth[a]+1;
order.push_back(x);
}
}
}
return {order,pare,depth};
}
std::vector<int> tree_diameter_path(std::vector<std::vector<int>> &G){
int n=G.size();
auto r=(std::get<0>(tree_order_pare_depth(G,0))).at(n-1);
std::vector<int> order,pare,depth,ans;
tie(order,pare,depth)=tree_order_pare_depth(G,r);
int ind=order[n-1];
while(ind!=-2){
ans.push_back(ind);
ind=pare[ind];
}
return ans;
}
//in[i] -> p[i]
//out[i] -> p[i+N]
std::vector<int> Euler_Tour(std::vector<std::vector<int>> &G,int root){
std::stack<int> s;
int n=G.size();
std::vector<int> p(n*2),seen(n);
s.push(root);
seen[root]=1;
for(int i=0;i<2*n;i++){
int a=s.top();
p[a]=i;
s.pop();
if(a<n){
s.push(a+n);
for(auto x:G[a]){
if(seen[x]==0){
s.push(x);
seen[x]=1;
}
}
}
}
return p;
}
#line 2 "/Users/Shared/po167_library/math/Binomial.hpp"
#line 5 "/Users/Shared/po167_library/math/Binomial.hpp"
namespace po167{
template<class T>
struct Binomial{
std::vector<T> fact_vec, fact_inv_vec;
void extend(int m = -1){
int n = fact_vec.size();
if (m == -1) m = n * 2;
if (n >= m) return;
fact_vec.resize(m);
fact_inv_vec.resize(m);
for (int i = n; i < m; i++){
fact_vec[i] = fact_vec[i - 1] * T(i);
}
fact_inv_vec[m - 1] = T(1) / fact_vec[m - 1];
for (int i = m - 1; i > n; i--){
fact_inv_vec[i - 1] = fact_inv_vec[i] * T(i);
}
}
Binomial(int MAX = 0){
fact_vec.resize(1, T(1));
fact_inv_vec.resize(1, T(1));
extend(MAX + 1);
}
T fact(int i){
if (i < 0) return 0;
while (int(fact_vec.size()) <= i) extend();
return fact_vec[i];
}
T invfact(int i){
if (i < 0) return 0;
while (int(fact_inv_vec.size()) <= i) extend();
return fact_inv_vec[i];
}
T C(int a, int b){
if (a < b || b < 0) return 0;
return fact(a) * invfact(b) * invfact(a - b);
}
T invC(int a, int b){
if (a < b || b < 0) return 0;
return fact(b) * fact(a - b) *invfact(a);
}
T P(int a, int b){
if (a < b || b < 0) return 0;
return fact(a) * invfact(a - b);
}
T inv(int a){
if (a < 0) return inv(-a) * T(-1);
if (a == 0) return 1;
return fact(a - 1) * invfact(a);
}
T Catalan(int n){
if (n < 0) return 0;
return fact(2 * n) * invfact(n + 1) * invfact(n);
}
T narayana(int n, int k){
if (n <= 0 || n < k || k < 1) return 0;
return C(n, k) * C(n, k - 1) * inv(n);
}
T Catalan_pow(int n,int d){
if (n < 0 || d < 0) return 0;
if (d == 0){
if (n == 0) return 1;
return 0;
}
return T(d) * inv(d + n) * C(2 * n + d - 1, n);
}
// retrun [x^a] 1/(1-x)^b
T ruiseki(int a,int b){
if (a < 0 || b < 0) return 0;
if (a == 0){
return 1;
}
return C(a + b - 1, b - 1);
}
// (a, b) -> (c, d)
// always x + e >= y
T mirror(int a, int b, int c, int d, int e = 0){
if (a + e < b || c + e < d) return 0;
if (a > c || b > d) return 0;
a += e;
c += e;
return C(c + d - a - b, c - a) - C(c + d - a - b, c - b + 1);
}
// return sum_{i = 0, ... , a} sum_{j = 0, ... , b} C(i + j, i)
// return C(a + b + 2, a + 1) - 1;
T gird_sum(int a, int b){
if (a < 0 || b < 0) return 0;
return C(a + b + 2, a + 1) - 1;
}
// return sum_{i = a, ..., b - 1} sum_{j = c, ... , d - 1} C(i + j, i)
// AGC 018 E
T gird_sum_2(int a, int b, int c, int d){
if (a >= b || c >= d) return 0;
a--, b--, c--, d--;
return gird_sum(a, c) - gird_sum(a, d) - gird_sum(b, c) + gird_sum(b, d);
}
// the number of diagonal dissections of a convex n-gon into k+1 regions.
// OEIS A033282
// AGC065D
T diagonal(int n, int k){
if (n <= 2 || n - 3 < k || k < 0) return 0;
return C(n - 3, k) * C(n + k - 1, k) * inv(k + 1);
}
};
}
#line 4 "/Users/Shared/po167_library/ds/Sparse_table.hpp"
namespace po167{
template<class T, T(*op)(T, T)>
struct Sparse_table{
int n;
int depth;
std::vector<std::vector<T>> val;
void init(std::vector<T> &v){
depth = 1;
n = v.size();
while ((1 << depth) <= n) depth++;
val.resize(depth);
val[0] = v;
for (int i = 1; i < depth; i++){
val[i].resize(n);
for (int j = 0; j <= n - (1 << i); j++){
val[i][j] = op(val[i - 1][j], val[i - 1][j + (1 << (i - 1))]);
}
}
}
Sparse_table(std::vector<T> v){
init(v);
}
Sparse_table(){}
// 0 <= l < r <= n
// if l == r : assert
T prod(int l, int r){
assert(0 <= l && l < r && r <= n);
int z=31-__builtin_clz(r-l);
return op(val[z][l], val[z][r - (1 << z)]);
}
};
}
#line 6 "/Users/Shared/po167_library/graph/tree/LCA.hpp"
namespace po167{
int op(int a, int b){
return std::min(a, b);
}
struct LCA{
Sparse_table<int, op> table;
std::vector<int> depth;
std::vector<int> E;
std::vector<int> order;
int var_num;
void init(std::vector<std::vector<int>> &g, int root = 0){
var_num = g.size();
assert(0 <= root && root < var_num);
std::vector<int> val;
depth.assign(var_num, -1);
depth[root] = 0;
E.resize(var_num);
std::vector<int> tmp;
order.clear();
tmp.reserve(var_num);
order.reserve(var_num);
int c = 0;
auto dfs = [&](auto self, int var, int pare) -> void {
E[var] = c++;
if (var != root) tmp.push_back(E[pare]);
order.push_back(var);
for (auto x : g[var]) if (depth[x] == -1){
depth[x] = depth[var] + 1;
self(self, x, var);
}
};
dfs(dfs, root, -1);
assert(c == var_num);
table.init(tmp);
}
void init(std::vector<int> &pare){
int root = -1;
int n = pare.size();
std::vector<std::vector<int>> g(n);
for (int i = 0; i < n; i++){
if (pare[i] < 0){
assert(root == -1);
root = i;
}
else{
assert(0 <= pare[i] && pare[i] < n);
g[pare[i]].push_back(i);
}
}
assert(root != -1);
init(g, root);
}
LCA (std::vector<std::vector<int>> g, int root = 0){
init(g, root);
}
LCA (std::vector<int> pare){
init(pare);
}
LCA(){
}
int lca(int a, int b){
assert(0 <= std::min(a, b) && std::max(a, b) < var_num);
if (a == b) return a;
if (E[a] > E[b]) std::swap(a, b);
return order[table.prod(E[a], E[b])];
}
int dist(int a, int b){
assert(0 <= std::min(a, b) && std::max(a, b) < var_num);
return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}
int back(int var, int len){
assert(len <= depth[var]);
if (len == 0) return var;
int l = 0, r = E[var];
while (r - l > 1){
int m = (l + r) / 2;
if (depth[var] - depth[order[table.prod(m, E[var])]] < len){
r = m;
}
else l = m;
}
return order[table.prod(l, E[var])];
}
// a -> b
int jump(int a, int b, int len){
int c = lca(a, b);
if (len <= depth[a] - depth[c]) return back(a, len);
len -= depth[a] - depth[c];
if (len <= depth[b] - depth[c]) return back(b, depth[b] - depth[c] - len);
return -1;
}
};
}
#line 94 "a.cpp"
using mint = atcoder::modint998244353;
void solve();
// POP'N ROLL MUSIC / TOMOO
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
rep(i, 0, t) solve();
}
void solve(){
int N;
cin >> N;
vector<int> A(N);
rep(i, 0, N) cin >> A[i];
const int L = 1'000'100;
vector<vector<int>> table(L);
rep(i, 2, L) if (table[i].empty()){
for (int j = i; j < L; j += i){
int tmp = j;
int c = 1;
while (tmp % i == 0){
tmp /= i;
c *= i;
table[j].push_back(c);
}
}
}
auto G = tree_in(N);
auto E = Euler_Tour(G, 0);
vector<int> order(N);
rep(i, 0, N) order[i] = i;
sort(all(order), [&](int l, int r){
return E[l] < E[r];
});
po167::LCA lc(G);
vector<int> la(L, -1);
po167::Binomial<mint> Bi;
vector<mint> ans(N, 1);
for (auto var : order){
ans[var] *= A[var];
int a = -1, b = -1;
for (auto x : table[A[var]]){
if (la[x] != -1){
if (a != la[x]) a = la[x], b = lc.lca(a, var);
ans[b] *= Bi.inv(table[x].front());
}
la[x] = var;
}
}
vector<int> pare, depth;
tie(order, pare, depth) = tree_order_pare_depth(G, 0);
reverse(all(order));
rep(i, 0 ,N - 1){
int a = order[i];
ans[pare[a]] *= ans[a];
}
for (auto x : ans) cout << x.val() << "\n";
}