Codeforces #206 Div1. C. Vasya and Beautiful Arrays

これは少しEditorialを見て解いた。
http://codeforces.com/contest/354/problem/C

問題

N要素の自然数列A[i]が与えられる。
ここで、Aの各要素を最大Kまで減らせるとき、最大公約数を最大化せよ。

解法

仮に最大公約数をDとする。
するとAの要素がD～(D+K)、2D～(2D+K)、3D～(3D+K)…にすべて収まるなら、題意を満たす。

よってAが高々10^6までであることを用いて、まず各数値が何回登場するかを求め、その部分和からAに含まれる数i以下の数T[i]を求めることができる。
あとはDを大きい順からgreedyに試して、(T[D+K]-T[D-1])+(T[2D+K]-T[2D-1])+...==NとなるDを求めればよい。

int N,K;
int B[2000001],T[2000001];


void solve() {
	int f,i,j,k,l, x,y,d;
	
	cin>>N>>K;
	FOR(i,N) B[GETi()]++;
	FOR(i,2000000) T[i+1]=T[i]+B[i+1];
	FOR(d,1000001) if(B[d]) break;
	
	for(;d>=2;d--) {
		x=0;
		if(d<=K) x=N;
		else {
			for(y=d;y<=1000000;y+=d) x+=T[y+K]-T[y-1];
		}
		if(x>=N) return _P("%d\n",d);
	}
	_P("1\n");
}

まとめ

Cとはいえ理解してしまえば簡単。