TopCoder SRM 599 Div1 Easy BigFatInteger

SRM599に参加。
EasyをResubmitで75ptしか得られなかったものの、Resubmitで得たテストケースを使って3challenge、125ptを追加してなんとかレートを維持した。
Mediumはまたもコーナーケースを落としてミス。

今回はMediumの正答者が少なかったので、Easyを1発正解するかMediumを通せば一気に順位が上がるはずだったのにもったいない。
http://community.topcoder.com/stat?c=problem_statement&pm=12867

問題

数A,Bが与えられる。
X=1から初めて、以下の処理を繰り返していく。

1. Xに任意の素数pを掛ける。
2. Xに任意のXの約数を掛ける

XをA**Bにするまでに必要な処理回数を答えよ。

解法

A**Bが素因数として素数P[i]をQ[i]個含むとする。
この数を再現するには、まず処理1で1回P[i]をXに掛け、あとはQ[i]に到達するまで処理2で倍々していけばよい。

この倍々処理はすべての素因数に対して同時に行うことが出来るので、結局解答は以下の通り。
Aを素因数分解したのちに各素因数の数にBを掛ける。

この素因数の種類だけ処理1を実行する。
素因数の乗数が最大のものQ[j]に対し、ceil(Q[j]*B)に至るまで処理2で倍々処理を繰り返す。
両処理の合計が答え。

過去に似たような問題があったためか、処理2の回数を求めるのにbitcountを使ってる人が結構いた。
まぁ自分の初回submitもそれで、サンプルが通ってしまうのが恐ろしい。

int NP,prime[100000];
const int prime_max = 1000000;
void cprime() {
	static int p[prime_max];
	int i,j;
	for(i=2;i<prime_max;i++) {
		if(p[i]) continue;
		prime[NP++]=i;
		for(j=i*2;j<prime_max;j+=i) p[j]=i;
	}
}

int p2[100000];

class BigFatInteger {
	public:
	int minOperations(int A, int B) {
		vector<ll> V;
		int i;
		NP=0;
		cprime();
		ZERO(p2);
		FOR(i,NP) {
			while(A%prime[i]==0) {
				A/=prime[i];
				p2[i]++;
			}
			
			if(p2[i]) V.push_back(p2[i]*(ll)B);
		}
		int r=V.size();
		sort(V.begin(),V.end());
		int aa=0;
		ll la=V[V.size()-1];
		while(1LL<<(aa+1)<=la) aa++;
		if(1LL<<aa==la) r+=aa;
		else r+=aa+1;
		
		return r;
		
	}
};

まとめ

もったいない結果だけど、ResubmitのおかげでChallengeできたし、レート維持しただけマシとするか…。