SRM 643 DIV1 Easy - TheKingsFactorization x○

問題


http://community.topcoder.com/stat?c=problem_statement&pm=13594&rd=16086

整数Nを素因数分解したい。
ただし、Nはとても大きいため、Nを素因数分解したときの答えの
昇順に1番目、3番目、、と一つ置きの因数が与えられる。
このとき、すべての因数を求める。

解き方


Nが最大で10^18のため計算量の考慮が必要。

まず、Nを与えられた素因数で割ってから残りの数を求めようとすると
{2,(2),2,(10^16)}のときO(10^8)となり計算量オーバー。

次に、与えられた素因数の間の数prime[i]とprime[i+1]の間を求めていくやり方も
{2,(2),10^16}のときO(10^16)となり計算量オーバー。

そこで、両方の判定を加えてあげることで
{2,(2),10^6,(10^11)}の場合でも、最大でO(10^6)に収められる。


コード


class TheKingsFactorization {

public: vector<long long> getVector(long long N, vector<long long> primes) {
int n=primes.size();
FORE(i,0,n)N/=primes[i];

vector<long long> ans=primes;
FORE(i,0,n-1){
for(long long j=primes[i];j<=primes[i+1] && j*j<=N;j++){
while(N%j==0){
ans.push_back(j);
N/=j;
}
}
}
if(N!=1)ans.push_back(N);

sort(all(ans));

return ans;
}

};
このエントリーをはてなブックマークに追加