問題
http://community.topcoder.com/stat?c=problem_statement&pm=2943&rd=5858
正の整数の集合が与えられ、この数の平方根を考える。
この平方根に対して足すことができるものを全てまとめて、最後に昇順にして返す。
解き方
全ての平方根に対して整数を切り出して、根が一緒のものをまとめる。
最後に切り出した整数をまた根の中に戻してあげて、昇順にソートすればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[1001];
class SumOfSquareRoots {
public:
vector<int> shortestList(vector<int> A) {
memset(dp,0,sizeof(dp));
FORE(i,0,A.size()){
int x=A[i];
int cost=1;
for(int j=2;j*j<=A[i];j++){
if(x%(j*j)==0){
while(x%(j*j)==0){
cost*=j;
x/=(j*j);
}
}
}
dp[x]+=cost;
}
vector<int> ans;
FORE(i,0,1001)if(dp[i])ans.push_back(dp[i]*dp[i]*i);
sort(all(ans));
return ans;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[1001];
class SumOfSquareRoots {
public:
vector<int> shortestList(vector<int> A) {
memset(dp,0,sizeof(dp));
FORE(i,0,A.size()){
int x=A[i];
int cost=1;
for(int j=2;j*j<=A[i];j++){
if(x%(j*j)==0){
while(x%(j*j)==0){
cost*=j;
x/=(j*j);
}
}
}
dp[x]+=cost;
}
vector<int> ans;
FORE(i,0,1001)if(dp[i])ans.push_back(dp[i]*dp[i]*i);
sort(all(ans));
return ans;
}
};