CFR 402 D. Upgrading Array ( Greedy )

Problem - D - Codeforces

題意：
給一個數列，以及一些厄運質數。一個數的價值等於，質因數分解後，非厄運質數數量 - 厄運質數數量。可以做任意次操作，每次操作選擇數列中一個下標，將該下標以前的所有數字都除以他們的共同最大因數。求最大總價值。

資料規模：
The first line contains two integers n and m (1 ≤ n, m ≤ 5000) showing how many numbers are in the array and how many bad prime numbers there are.
The second line contains n space-separated integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 1e9) — array a. The third line contains m space-separated integers b1, b2, ..., bm (2 ≤ b1 < b2 < ... < bm ≤ 1e9) — the set of bad prime numbers.
TL: 1000 ms
ML: 256 MB

解法：
如果先對某個下標 i 操作，就不能接著對另一個下標 j，i ≤ j 進行操作，但反之可以。因此要由右而左考慮。考慮這樣的貪婪法，只要能將數列的價值提升，就進行操作。這是對的，因為對於某個除以數 v 的操作，在右邊做一定比在左邊做優 ( 對每個數字有相同提升量，但有更多數字可以提升 )，又有當前的點不操作，左邊若要操作一定是除以數 v * t ( t 為整數 ) 的，所以肯定早做比較優。

時間 / 空間複雜度：
O( N^1.5 * lg M )

int N, M;
vi A;
vi B;

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

vi pgcd;
set< int > bad_prime;

void preprocess(){
  pgcd = vi( N + 1 );
  for( int i = 0; i < N; ++i ){
    pgcd[ i + 1 ] = __gcd( pgcd[ i ], A[ i ] );
  }
  for( int i = 0; i < M; ++i ){
    bad_prime.emplace( B[ i ] );
  }
}

int evaluate( int v ){
  int res = 0;
  for( int i = 2; i * i <= v; ++i ){
    while( v % i == 0 ){
      v /= i;
      if( bad_prime.count( i ) ){
        --res;
      } else{
        ++res;
      }
    }
  }
  if( v > 1 ){
    if( bad_prime.count( v ) ){
      --res;
    } else{
      ++res;
    }
  }
  return res;
}

void solve(){
  ll ans = 0LL;
  int del = 1;
  for( int i = N; i >= 1; --i ){
    int v = evaluate( pgcd[ i ] / del );
    if( v < 0 ){
      del = pgcd[ i ];
    }
    ans += evaluate( A[ i - 1 ] / del );
  }
  cout << ans << endl;
}