結果

問題 No.3250 最小公倍数
ユーザー jiangxinyang
提出日時 2025-08-30 11:32:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,014 bytes
コンパイル時間 2,757 ms
コンパイル使用メモリ 211,372 KB
実行使用メモリ 220,800 KB
最終ジャッジ日時 2025-08-30 11:32:45
合計ジャッジ時間 22,342 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

inline int read();
void write(int);
void writeln(int);

const int P = 998244353;
const int A = 1e6;

int n;
vector<int> prime;

void getprime() {
    prime.resize(A + 1);
    iota(prime.begin(), prime.end(), 0);
    for(int i = 2; i * i <= A; i++) 
        if(prime[i] == i) 
			for(int j = i * i; j <= A; j += i) 
				if(prime[j] == j) 
					prime[j] = i;
	return ;
}

void fact(int x, unordered_map<int, int>& f) {
    f.clear();
    if(x == 1) return;
    while(x > 1) {
        int p = prime[x];
        int cnt = 0;
        while(x % p == 0) x /= p, cnt++;
        f[p] = cnt;
    }
}

long long qpow(long long p, int e) {
    long long ret = 1;
    p %= P;
    while(e) {
        if(e & 1) ret = (ret * p) % P;
        p = (p * p) % P;
        e >>= 1;
    }
    return ret;
}

int main() {
	
    getprime();

    n = read();
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) a[i] = read();

    vector<vector<int> > G(n + 1);
    for(int i = 0; i < n - 1; i++) {
        int u = read(), v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }

    vector<int> fa(n + 1, -1);
    queue<int> que;
    
    que.push(1);
    fa[1] = 0;
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        for(int v : G[u]) if(fa[v] == -1) fa[v] = u, que.push(v);
    }
    vector<vector<int> > cd(n + 1);
    for(int v = 2; v <= n; ++v) cd[fa[v]].push_back(v);
    vector<unordered_map<int, int> > f(n + 1);
    for(int i = 1; i <= n; i++) fact(a[i], f[i]);
    vector<int> cct(n + 1, 0);
    for(int u = 1; u <= n; u++) cct[u] = cd[u].size();
    queue<int> q;
    for(int u = 1; u <= n; u++) if(cct[u] == 0) q.push(u);
    vector<int> ans(n + 1);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int v : cd[u]) {
            if(f[u].size() < f[v].size()) swap(f[u], f[v]);
            for(const auto& kv : f[v]) {
                int p = kv.F, e = kv.S;
                auto it = f[u].find(p);
                if(it == f[u].end()) f[u][p] = e;
                else it->S = max(it->S, e);
            }
            f[v].clear();
        }
        long long res = 1;
        for(const auto& kv : f[u]) res = res * qpow(kv.F, kv.S) % P;
        ans[u] = res;
        int p = fa[u];
        if(p != 0) { if(--cct[p] == 0) q.push(p); }
    }

    for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);

//	printf("\nThe time used: ");
//	printf("%.2lfs",(double)clock()/CLOCKS_PER_SEC);

	return 0;

}

inline int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while( !(ch >= '0' && ch <= '9') ) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		res = (res << 1) + (res << 3) + (ch ^ 48);
		ch = getchar();
	}
	return res * f;
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10;
		x /= 10;
	} while(x);
	while(top) putchar(sta[--top] ^ 48);
}

void writeln(int x) {
	write(x);
	putchar('\n');
}
0