TopCoder SRM 643 Div1 Easy、Div2 Medium TheKingsFactorization

SRM643に参加。
Easyが遅く、MediumがResubmitだったけど、幸い2チャレンジ取って久々に2完したおかげで結構好順位。
Resubmitが悔やまれるなぁ。
http://community.topcoder.com/stat?c=problem_statement&pm=13594

問題

大きな数Nを素因数分解せよ。
ヒントとして、分解後の素因数を昇順に並べたとき、奇数番目の要素P[i]が与えられる。

解法

まずNを各P[i]で割っておく。
後はP[i]からP[i+1]の間の数でNを割れるものを探す。

ただし、N=2*大きな素数*大きな素数だったりするとこのままでは計算量がでTLEするので何かしら探索量を減らす必要がある。
例えばP[i]=小さな素数、P[i+1]=大きな素数とすると、以下の２つの方法の何れかで探索量を減らせる。

• 残されたNに対し、√Nまで探索する。
• Nがまだ分解できる場合、次の素数はP[i+1]以上である。よって探索する素数pはN/p≧P[i+1]の範囲まで探索する。

上記のいずれをとっても、探索回数をに抑えられる。

class TheKingsFactorization {
	public:
	vector<long long> getVector(long long N, vector<long long> P) {
		int i;
		vector<ll> V=P;
		int L=P.size();
		
		FOR(i,L) N/=P[i];
		FOR(i,L-1) {
			for(ll x=P[i];x<=P[i+1];x++) {
				if(N%x==0) {
					N/=x;
					V.push_back(x);
					break;
				}
				if(N/x<P[i+1]) break;
			}
		}
		if(N>1) V.push_back(N);
		sort(V.begin(),V.end());
		return V;
		
	}
}

まとめ

本番慎重になってSubmitが遅かったけど、その分のコードがダメになることに気づけて2Chal取れた。