AtCoder ABC #191 : F - GCD or MIN

今回CとかDが妙に面倒だね。
https://atcoder.jp/contests/abc191/tasks/abc191_f

問題

N個の正整数列Aが与えられる。
2要素個を選んで取り除き、替わりに両者のGCDかMIN1つ追加する、という作業を繰り返す。
最後に1要素が残った段階で、取りえる値は何通りあるか。

解法

GCD(a,b)≦MIN(a,b)なので、残る値は

• min(A)以下
• いくつかの要素の最大公約数

の両方を満たすものである。
そのようなものを数え上げよう。

f(k) := Aのうちkの倍数であるもののGCD
とする。f(k)=kなら、Aの最大公約数としてkを作れることを示す。
Aの各要素xについて、約数dを求め、f(d) = GCD(d,f(d))でこの値を更新していくとよい。

int N;
int A;
map<int,int> M;
unordered_map<int,int> U;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int mi=1<<30;
	FOR(i,N) {
		cin>>A;
		mi=min(mi,A);
		vector<int> V;
		for(j=1;j*j<=A;j++) if(A%j==0) V.push_back(j),V.push_back(A/j);
		
		FORR(v,V) U[v]=__gcd(U[v],A);
	}
	int ret=0;
	FORR2(a,b,U) if(a==b&&a<=mi) ret++;
	cout<<ret<<endl;
	
}

まとめ

Dで無駄ハマリを繰り返した。