Codeforces ECR #009 : D. Longest Subsequence

妙にE,FのTLが厳しい今回。Eが解けたので割と良い順位だった。
http://codeforces.com/contest/632/problem/D

問題

N個の整数A[i]が与えられる。
これらの整数を幾つか選択し、そのLCMを求める。
LCMがM以下のもののうち、要素数が最大である選択例を挙げよ。

解法

A中にある整数xの登場回数をxとする。
最終的なLCMがxの倍数であるなら、xは選択要素として含められる。
そこで、各xについて、C[x*k] += C[x]の要領で数え上げることで、LCMの約数を求めていこう。
(xは大きい順に処理すること)

あとはC[x]が最大となるxのうち最小のものを答えよう。

int N,M;
int A[1010101];
int V[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]<=M) V[A[i]]++;
	}
	for(i=M;i>=1;i--) {
		for(j=i*2;j<=M;j+=i) V[j]+=V[i];
	}
	int ma=0,mai=0;
	for(i=M;i>=1;i--) if(V[i]>ma) ma=V[i],mai=i;
	
	if(ma==0) return _P("1 0\n");
	
	vector<int> VV;
	ll LCM=1;
	FOR(i,N) if(mai%A[i]==0) {
		VV.push_back(i+1);
		LCM=LCM*A[i]/__gcd((int)LCM,A[i]);
	}
	_P("%d %d\n",(int)LCM,VV.size());
	FOR(i,VV.size()) _P("%d%s",VV[i],(i==VV.size()-1)?"\n":" ");
	
}

まとめ

これは割とすんなり。