Codeforces ECR #045 : G. GCD Counting

普段のECRに比べるとラク。
http://codeforces.com/contest/990/problem/G

問題

木を成すグラフが与えられる。
各頂点には正整数が設定されている。
任意の２頂点を結ぶパスについて、パス上の頂点の整数のGCDを取ることを考える。
その結果はが1～2*10^5となるのはそれぞれ何通りか。

解法

子頂点から順に、「自身のSubTreeから自身までのGCDの値とその登場回数」をmap等で管理していき、マージしていけばよい。
微妙にTLEが厳しいので、定数倍高速化が必要かも。

int N;
int A[202020];
vector<int> E[202020];
ll ret[202020];
map<int,int> M[202020];

void dfs(int cur,int pre) {
	ret[A[cur]]++;
	
	M[cur][A[cur]]=1;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		FORR(m,M[e]) FORR(c,M[cur]) {
			int g=__gcd(m.first,c.first);
			ret[g]+=1LL*m.second*c.second;
		}
		FORR(m,M[e]) M[cur][__gcd(A[cur],m.first)]+=m.second;
		M[e].clear();
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,0);
	for(i=1;i<=200000;i++) if(ret[i]) cout<<i<<" "<<ret[i]<<endl;
	
}

まとめ

まぁ解法が自明ということで教育的ではあるが。