CFR 757 B. Bash's Big Day ( Sieve )

Problem - B - Codeforces

題意：
求最大團大小，滿足團裡所有 S[ i ] 的最大公因數不為 1。

資料規模：
1 ≤ N ≤ 1e5
1 ≤ S[ i ] ≤ 1e5
TL: 2000 ms
ML: 512 MB

解法：
如果某個最大公因數 x 的倍數數量是最大可能的，那麼顯然對 x 的所有非 1 因數，倍數數量也是最大可能的。因此可以只分別檢查所有質數的倍數數量。

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

int N;
vi S;

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

const int MAXS = ( int ) 1e5;

int np[ MAXS + 1 ];

void preprocess(){
  vi rg( MAXS + 1 );
  for( int i = 0; i < N; ++i ){
    ++rg[ S[ i ] ];
  }
  for( int i = 2; i <= MAXS; ++i ){
    if( np[ i ] ) continue;
    for( int j = i + i; j <= MAXS; j += i ){
      np[ j ] = 1;
      rg[ i ] += rg[ j ];
    }
  }
  int ans = 1;
  for( int i = 2; i <= MAXS; ++i ){
    upmax( ans, rg[ i ] );
  }
  cout << ans << endl;
}