CFR 251 E. Devu and Birthday Celebration ( Inclusion Exclusion, Number Theory )

Problem - E - Codeforces

題意：
Q 筆詢問：
有 N 顆糖果要分給 F 個人，每個人至少拿到一顆，但希望每個人的糖果個數的最大公因數為 1。求方法數模上 1e9 + 7。

資料規模：
1 ≤ Q ≤ 1e5
1 ≤ F ≤ N ≤ 1e5
時間限制： 5000 ms
空間限制： 256 MB

解法：
考慮 N 顆糖果隨便分給 F 個不同的人，每個人至少拿到一顆的方法數。那相當是 N 顆糖果裡有 N - 1 個縫隙，要選 F - 1 個當作隔板，因此為 C( N - 1, F - 1 )。我們想從 C( N - 1, F - 1 ) 不重複地扣去所有，拿 N / p 顆糖果分給 F 個人的方案數 ( p 為非 N 的質因數 )，因為這些方案乘上 p 就會是原本多算的部分。
根據經驗很直覺地用 Inclusion Exclusion Principle，因為小於 1e5 的數最多只有 8 個質因數 ( 2 * 3 * 5 * .. )，所以做一次的複雜度只有 2^8。
最後要小心當 F = 1 的時候，如果 N > 1，最大公因數就一定會大於 1，因此對應的方案數為 0。

時間 / 空間複雜度：
O( N + Q * 2^8 )

const int MOD7 = ( int ) 1e9 + 7;
const int MAXN = ( int ) 1e5;

int Q;

void init(){

}

int int_pow( int v, int p ){
  if( v == 0 and p > 0 ){
    return 0;
  }
  int res = 1;
  while( p ){
    if( p & 1 ){
      res = 1LL * res * v % MOD7;
    }
    p >>= 1;
    v = 1LL * v * v % MOD7;
  }
  return res;
}

int mod_inv( int v ){
  return int_pow( v, MOD7 - 2 );
}

int fact[ MAXN + 1 ];
int inv_fact[ MAXN + 1 ];

void preprocess(){
  for( int i = fact[ 0 ] = inv_fact[ 0 ] = 1; i <= MAXN; ++i ){
    fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD7;
    inv_fact[ i ] = mod_inv( fact[ i ] );
  }
}

int C( int n, int m ){
  if( n < m ){
    return 0;
  }
  int res = 1LL * fact[ n ] * inv_fact[ m ] % MOD7;
  res = 1LL * res * inv_fact[ n - m ] % MOD7;
  return res;
}

void solve(){
  cin >> Q;
  for( int kase = 0; kase < Q; ++kase ){
    int N, F; cin >> N >> F;
    if( F == 1 ){
      cout << "01"[ N == 1 ] << endl;
      continue;
    }
    vi pf;
    int _n = N;
    for( int i = 2; i * i <= N; ++i ){
      if( _n % i != 0 ) continue;
      pf.emplace_back( i );
      while( _n % i == 0 ){
        _n /= i;
      }
    }
    if( _n != 1 and _n != N ){
      pf.emplace_back( _n );
    }
    int ans = C( N - 1, F - 1 );
    for( int s = 1; s < 1 << ( int ) pf.size(); ++s ){
      int n = N;
      for( int i = 0; i < pf.size(); ++i ){
        if( s & 1 << i ){
          n /= pf[ i ];
        }
      }
      int sign = ( int ) __builtin_popcount( s ) & 1;
      ( ans += ( sign ? -1 : 1 ) * C( n - 1, F - 1 ) ) %= MOD7;
    }
    if( ans < 0 ) ans += MOD7;
    cout << ans << endl;
  }
}