SRM 409: MagicalSpheres

(問題概要)
本物がspheresCount個、偽物がfakeSpheresCount個、全体からspheresCount個選んで全部正しいかを試す。
全通りを何グループかで試すとき、各グループが同じ通り数を試すには、gnomesAvailable以下で最大何グループ選べるか。
(nCk % m == 0 となる gnomeAvailable以下の最大のmを計算)

(解法)
gnomeAvailable以下の数を全部試す。
素因数分解してチェック。素因数分解は頑張らなくても計算量的に余裕。

#include <cstdio>
typedef long long ll;

#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class MagicalSpheres {
public:
  int divideWork(int spheresCount, int fakeSpheresCount, int gnomesAvailable);
};

vector<pair<int, int> > factorize(int n){
  vector<pair<int, int> > ret;

  for(int i = 2; i * i <= n; i++){
    if(n % i == 0){
      int cnt = 0;
      while(n % i == 0){
	n /= i;
	cnt++;
      }
      ret.push_back(make_pair(i, cnt));
    }
  }
  if(n > 1) ret.push_back(make_pair(n, 1));

  return ret;
}

bool check(int n, int k, const vector<pair<int, int> > &fact){
  REP(i, fact.size()){
    const int fct = fact[i].first;
    const int cnt = fact[i].second;

    int c = 0;
    ll f = fct;

    while(f <= n){
      c += n / f;
      c -= (n - k) / f;
      c -= k / f;

      f *= fct;
    }

    // printf("%d : %d\n", fct, c);

    if(c < cnt) return false;
  }

  return true;
}

int MagicalSpheres::divideWork(int spheresCount, int fakeSpheresCount, int gnomesAvailable){
  for(int i = gnomesAvailable; i > 0; i--){
    if(check(spheresCount + fakeSpheresCount, spheresCount, factorize(i)))
      return i;
  }
  return 0;
}