結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<int idx>
struct Montgomery{
    //2^62未満&奇数modのみ.
    //初めにsetmodする.
    using u64 = uint64_t;
    using u128 = __uint128_t;
 
    private:
    static u64 mod,N2,Rsq; //N*N2≡1(mod N);
    //Rsq = R^2modN; R=2^64.
    u64 v = 0;
    public:
    long long val()const{return reduce(v);}
    static constexpr u64 getmod(){return mod;}
    static void setmod(u64 m){
        assert(m<(1LL<<62)&&(m&1));
        mod = m; N2 = mod;
        for(int i=0; i<5; i++) N2 *= 2-N2*mod;
        Rsq = (-u128(mod))%mod;
    }
    //reduce = T*R^-1modNを求める.
    u64 reduce(const u128 &T)const{
        //T*R^-1≡(T+(T*(-N2))modR*N)/R 2N未満なので-N必要かだけで良い.
        u64 ret = (T+u128(((u64)T)*(-N2))*mod)>>64;
        if(ret >= mod) ret -= mod;
        return ret;
    }
    //初期値<mod. 初めにw*R modN...->reduce(R^2)でok.
    Montgomery(){v = 0;} Montgomery(long long w):v(reduce(u128(w)*Rsq)){}
 
    Montgomery& operator=(const Montgomery &b) = default;
    Montgomery operator-()const{return Montgomery()-Montgomery(*this);}
    Montgomery operator+(const Montgomery &b)const{return Montgomery(*this)+=b;}
    Montgomery operator-(const Montgomery &b)const{return Montgomery(*this)-=b;}
    Montgomery operator*(const Montgomery &b)const{return Montgomery(*this)*=b;}
    Montgomery operator/(const Montgomery &b)const{return Montgomery(*this)/=b;}
    Montgomery& operator+=(const Montgomery &b){
        v += b.v;
        if(v >= mod) v -= mod;
        return (*this);
    }
    Montgomery& operator-=(const Montgomery &b){
        v += mod-b.v;
        if(v >= mod) v -= mod;
        return (*this);
    }
    Montgomery& operator*=(const Montgomery &b){
        v = reduce(u128(v)*b.v);
        return (*this);
    }
    Montgomery& operator/=(const Montgomery &b){
        (*this) *= b.inv();
        return (*this);
    }
    Montgomery pow(u64 b)const{
        Montgomery ret = 1,p = (*this);
        if(b < 0) p = p.inv(),b = -b;
        while(b){
            if(b&1) ret *= p;
            p *= p; b >>= 1;
        }
        return ret;
    }
    Montgomery inv()const{return pow(mod-2);}
 
    bool operator!=(const Montgomery &b)const{return v!=b.v;}
    bool operator==(const Montgomery &b)const{return v==b.v;}
};
template<int idx>  uint64_t Montgomery<idx>::mod;
template<int idx>  uint64_t Montgomery<idx>::N2;
template<int idx>  uint64_t Montgomery<idx>::Rsq;
using mint = Montgomery<0>;

random_device rnd;
mt19937 mt(rnd());

int main(){
    mint::setmod(998244353);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int Limit = 1001001; //Limit->必要なサイズ fac->x! facinv->1/x! inv->1/x.
    vector<mint> fac(Limit+1,1),facinv(Limit+1),V(Limit+1);
    for(int i=0; i<=Limit; i++) V.at(i) = i;
    {
        int mod = mint::getmod(),invstart = min(mod-1,Limit); 
        for(int i=1; i<=Limit; i++) fac.at(i) = fac.at(i-1)*V.at(i);
        facinv.at(invstart) = fac.at(invstart).inv();
        for(int i=invstart-1; i>=0; i--) facinv.at(i) = facinv.at(i+1)*V.at(i+1);
    }
    vector<mint> inv(Limit+1); for(int i=1; i<=Limit; i++) inv.at(i) = fac.at(i-1)*facinv.at(i); //必要なら解放.

    int Need = 1001001;
    vector<vector<pair<int,int>>> Pf(Need+1);
    vector<bool> prime(Need+1,true);
    prime.at(0) = false; prime.at(1) = false;
    for(int i=2; i<=Need; i++){
        if(!prime.at(i)) continue;
        Pf.at(i) = {{i,i}};
        for(int k=i+i; k<=Need; k+=i){
            prime.at(k) = false;
            int f = 1,k2 = k;
            while(k2%i == 0) f *= i,k2 /= i;
            Pf.at(k).push_back({i,f});
        }
    }

    int N; cin >> N;
    vector<int> A(N,510510);
    for(auto &a : A) cin >> a;
    vector<vector<int>> Graph(N);
    for(int i=0; i<N-1; i++){
        int u = i/2+1,v = u*2+i%2;
        cin >> u >> v;
        u--; v--;
        Graph.at(u).push_back(v);
        Graph.at(v).push_back(u);
    }
    {
        vector<int> siz(N);
        auto dfs = [&](auto dfs,int pos,int back) -> int {
            int ret = 1;
            for(auto to : Graph.at(pos)) if(to != back) ret += dfs(dfs,to,pos);
            siz.at(pos) = ret;
            return ret;
        };
        dfs(dfs,0,-1);
        for(auto &g : Graph) sort(g.begin(),g.end(),[&](auto a,auto b){return siz.at(a)>siz.at(b);});
    }

    vector<mint> answer(N);
    {
        vector<int> C(1001001),best(1001001,1); C.at(1) = 1;
        mint now = 1;
        auto dfs = [&](auto dfs,int pos,int back,bool leader) -> void {
            int big = -1;
            for(auto to : Graph.at(pos)){
                if(to == back) continue;
                big = to; break;
            }
            for(auto to : Graph.at(pos)){
                if(to == back || to == big) continue;
                dfs(dfs,to,pos,false);
            }
            if(big != -1) dfs(dfs,big,pos,true);
            {
                auto dfs2 = [&](auto dfs2,int po,int ba) -> void {
                    for(auto [p,v] : Pf.at(A.at(po))){
                        if(best.at(p) < v){
                            now *= inv.at(best.at(p));
                            now *= V.at(v);
                            best.at(p) = v;
                        }
                        C.at(v)++;
                    }
                    for(auto to : Graph.at(po)) if(to != ba) dfs2(dfs2,to,po);
                };
                for(auto to : Graph.at(pos)){
                    if(to == back || to == big) continue;
                    dfs2(dfs2,to,pos);
                }
            }
            for(auto [p,v] : Pf.at(A.at(pos))){
                if(best.at(p) < v){
                    now *= inv.at(best.at(p));
                    now *= V.at(v);
                    best.at(p) = v;
                }
                C.at(v)++;
            }

            answer.at(pos) = now;
            if(!leader){
                auto dfs2 = [&](auto dfs2,int po,int ba) -> void {
                    for(auto to : Graph.at(po)){
                        if(to == ba) continue;
                        dfs2(dfs2,to,po);
                    }
                    for(auto [p,v] : Pf.at(A.at(po))){
                        C.at(v)--;
                        best.at(p) = 1;
                    }
                };
                now = V.at(1),dfs2(dfs2,pos,back);
            }
        };
        dfs(dfs,0,-1,true);
    }
    for(auto &a : answer) cout << a.val() << "\n";
}
0