yukicoder : No.2497 GCD of LCMs

こちらはすんなりだった。
https://yukicoder.me/problems/no/2497

問題

無向グラフが与えられる。
各点には正整数が設定されている。
各点vに対し、以下を求めよ。

• 点1→点vに至るあらゆるパスを考える。各パスにおいて、通過した頂点の正整数の最小公倍数を考えたとき、その最大公約数は何か。

解法

素因数pごとに考える。
B(p,v) := 頂点vの値をpで割ったとき、何回割り切れるか
とする。
dp(p,v) := 頂点1からvに至るB(p,v)の最大値の最小値
上記値は単純なダイクストラ法で計算可能である。
あとは解にp^(dp(p,v))を掛ければよい。

int N,M;
int A[250];
int B[250];
int D[250];
vector<int> E[2020];
ll ret[255];
const ll mo=998244353;

set<ll> enumpr(ll n) {
	set<ll> V;
	for(ll i=2;i*i<=n;i++) while(n%i==0) V.insert(i),n/=i;
	if(n>1) V.insert(n);
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	set<int> S;
	FOR(i,N) {
		cin>>A[i];
		auto a=enumpr(A[i]);
		FORR(v,a) S.insert(v);
		ret[i]=1;
	}
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	FORR(p,S) {
		FOR(i,N) {
			x=A[i];
			B[i]=0;
			D[i]=1<<20;
			while(x%p==0) {
				B[i]++;
				x/=p;
			}
		}
		priority_queue<pair<int,int>> Q;
		D[0]=B[0];
		Q.push({-D[0],0});
		while(Q.size()) {
			int co=-Q.top().first;
			int cur=Q.top().second;
			Q.pop();
			if(D[cur]!=co) continue;
			FORR(e,E[cur]) if(chmin(D[e],max(B[e],co))) Q.push({-D[e],e});
		}
		FOR(i,N) {
			FOR(j,D[i]) ret[i]=ret[i]*p%mo;
		}
	}
	FOR(i,N) cout<<ret[i]<<endl;
		
}

まとめ

シンプルな問題。