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]=大きな素数とすると、以下の2つの方法の何れかで探索量を減らせる。
上記のいずれをとっても、探索回数をに抑えられる。
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取れた。