CFR 354 C. Vasya and Beautiful Arrays ( Math, Harmonic Series, Number Theory )

題意：
給你一個數列，有 N 個元素，再給你一個整數 K。你可以分別將數列中每個元素 a[ i ] 變為 [ max( 1, a[ i ] - K ), a[ i ] ] 中任意一個整數。求變換過的數列的最大可能最大公因數。

資料規模：
1 ≤ n ≤ 3e5
1 ≤ k ≤ 1e6
1 ≤ a[ i ] ≤ 1e6
TL: 1000 ms
ML: 256 MB

解法：
感覺是時候考慮 a 中的最大值或最小值和 K 的關係，並討論一波。
發現當 min{ a } <= K 時，因為答案不能比 min{ a } 大，但所有比 min{ a } 大的數都顯然能減 [ 0, K ] 中的一個整數成為 min{ a }，所以答案一定是 min{ a }。所以接著考慮當 min{ a } > K 時怎麼計算。
顯然答案一定至少是 K。所以考慮枚舉答案為 [ K + 1, min{ a } ] 中的整數。
在這裡感覺就算不能線性，也要來個 O( N lg N ) 之類的東西，而整數論的題目最愛出 Harmonic Series：
Sigma{ 1 / n, for all 1 ≤ n } = lg N
所以想想看能不能找出這種形式的算法。
想一想，假設我們枚舉到答案為某個整數 p，因為 p > K，所以 [ p - K, p ] < [ 2 * p - K, 2 * p ] < [ 3 * p - K, 3 * p ] < ...
而我們想知道的是這些區間是否完全覆蓋 a，所以如果預處理 a 的分布的前綴和，事實上求的是前綴和中這些區間的總和是否為 N。
需要枚舉的區間數，換句話說需要枚舉的 p 的係數數量，顯然是 max{ a } / p，因此總複雜度是：
Sigma{ max{ a } / p , for all K + 1 ≤ p ≤ min{ a } }
根據 Harmonic Series 為 O( max{ a } lg max{ a } )

時間 / 空間複雜度：
O( max{ a } lg max{ a } )

閒話：
這個 Round 出的題目品質都很優，有空看看其他題。

int N, K;
vi A;

void init(){
  cin >> N >> K;
  A = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
}

int min_A;
int max_A;
vi ps;

void preprocess(){
  min_A = *min_element( A.begin(), A.end() );
  max_A = *max_element( A.begin(), A.end() );
  if( min_A <= K ){
    cout << min_A << endl;
    exit( 0 );
  } // now minA > K
  ps = vi( max_A + 1 );
  for( int i = 0; i < N; ++i ){
    ++ps[ A[ i ] ];
  }
  for( int i = 0; i + 1 <= max_A; ++i ){
    ps[ i + 1 ] += ps[ i ];
  }
  for( int i = min_A; i > K; --i ){
    int sum = 0;
    for( int j = 1; j <= max_A / i; ++j ){
      sum += ps[ min( max_A, j * i + K ) ] - ps[ j * i - 1 ];
    }
    if( sum == N ){
      cout << i << endl;
      exit( 0 );
    }
  }
  cout << K << endl;
}