Codeforces 354C Vasya and Beautiful Arrays

問題

数列a[i]が与えられる。
それぞれの項から、引いた後0以下にならないように最大kを引くことができる。

なるべく出来た数列の最大公約数を大きくしたい。
最大値を求めよ。

制約条件

a[i]≦10^6
n≦3*10^5

方針

パソコン甲子園のモジュロ・クエリ（そのままの解法が使える）だった。
http://web-ext.u-aizu.ac.jp/pc-concours/2013/programming/p_pastexam.html
（2012年本選5）
なんか見たことある問題だと思った。

まず数列aはuniqueしてよい。
最大公約数qを決めうちして作れるか調べる。

モジュロクエリと同様にして、L[i]という配列を作ってai未満の最大のajをO(1)で求めることができれば、
計算量O(A / q)でai%qの最大値が求まる。（Aはmax{a[i]})

これを全てのqについて調べると、計算量はA / 1 + A / 2 + A / 3 + ... + A / A = O(AlogA)
a[i]を0にしてしまってはいけないことにだけ注意する。

ソースコード

int n, k, a[300000], l[1000100];

int main(){
	
	cin >> n >> k;
	rep(i, n) cin >> a[i];
	sort(a, a + n);
	n = unique(a, a + n) - a;
	
	l[0] = -1;
	for(int i = 0, j = 0; j <= 1000010; j++){
		if(i < n && a[i] == j) l[j + 1] = a[i++];
		else l[j + 1] = l[j];
	}
	
	for(int i = a[0]; i > 1; i--){
		bool ok = 1;
		
		for(int j = a[n-1]; j >= a[0]; ){
			if(j % i > k || j == a[0] && j < i){
				ok = 0;
				break;
			}
			j -= j % i;
			j = l[j];
		}
		
		if(ok){
			cout << i << endl;
			return 0;
		}
	}
	cout << 1 << endl;
	return 0;
}