問題
http://community.topcoder.com/stat?c=problem_statement&pm=8763&rd=12172
ある整数ｎが与えられる。
このｎが素数の階乗で表せるならその素数と階乗数を返す。
そのように表せられなければ空の文字列を返す。
解き方
nの最大は10^18で全探索できないが、
2乗の場合を除けば探索範囲はO(10^6)となり全探索可能。
2乗の場合の計算はdouble*double==longにならないよう、型を一致させることに注意。
コード
class StrongPrimePower {
public: vector<int> baseAndExponent(string n) {
vector<int> ans;
long long x;
stringstream out(n);
out>>x;
for(int i=2;i<=1000000 && i<x;i++)if(x%i==0){
long long tmp=x;
int cnt=0;
while(tmp%i==0){
tmp/=i;
cnt++;
}
if(tmp==1){
ans.push_back(i);
ans.push_back(cnt);
return ans;
}
return ans;
}
long long y=sqrt((double)x);
if(y*y==x){
ans.push_back(y);
ans.push_back(2);
}
return ans;
}
};
public: vector<int> baseAndExponent(string n) {
vector<int> ans;
long long x;
stringstream out(n);
out>>x;
for(int i=2;i<=1000000 && i<x;i++)if(x%i==0){
long long tmp=x;
int cnt=0;
while(tmp%i==0){
tmp/=i;
cnt++;
}
if(tmp==1){
ans.push_back(i);
ans.push_back(cnt);
return ans;
}
return ans;
}
long long y=sqrt((double)x);
if(y*y==x){
ans.push_back(y);
ans.push_back(2);
}
return ans;
}
};