Codeforces Round #206 (Div. 1) C. Vasya and Beautiful Arrays
解法
配列がすべて d の倍数になるように出来るとすると, 配列のすべての数が m*d + x (x は min(k, d-1) 以下の数)という形で表せることになるので, このようになっているかを調べます。d を全列挙したとしても, これを調べるのにかかる時間は, D を配列 a の最大値として,
D/1 + D/2 + D/3 + ...
となり, これは D log D に収束するので, 時間内に答えを求めることが出来ます。
const int MAXN = 300030; const int MAXK = 1000000; int s[2*MAXK+1]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n, k; cin >> n >> k; for (int i = 0; i < n; i++) { int a; cin >> a; s[a]++; } for (int i = 1; i <= 2*MAXK; i++) { s[i] += s[i-1]; } for (int d = MAXK; d >= 1; d--) { int cnt = 0; for (int x = d; x <= MAXK; x+=d) { cnt += s[x+min(d-1, k)] - s[x-1]; if (cnt >= n) { cout << d << endl; return 0; } } } assert(true); return 0; }