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; }