問題
http://community.topcoder.com/stat?c=problem_statement&pm=14072&rd=16552
解き方
素数を考えると、素数自身は交換対象とならない。
よって、何度交換が発生しても、ｎはｎより小さい素数とｎより大きい素数の
間に収まる。
素数の間隔は６００以内におさまるので、その間の全ての数の約数を調べて
シミュレーションし、最終的なｎの収束点が答えになる。
コード
class Procrastination {
public: long long findFinalAssignee(long long n) {
long long L=max(2LL,n-600),R=n+600;
set<long long> s;
for(long long i=L;i<=R;i++){
for(long long j=2;j*j<=i;j++){
if(i%j==0){
s.insert(j);
s.insert(i/j);
}
}
}
vector<long long> vx;
for(set<long long>::iterator it=s.begin();it!=s.end();it++){
vx.push_back(*it);
}
sort(all(vx));
FORE(i,0,vx.size()){
if((n-1)%vx[i]==0 && n-1>vx[i])n--;
else if(n%vx[i]==0 && n>vx[i])n++;
}
return n;
}
};
public: long long findFinalAssignee(long long n) {
long long L=max(2LL,n-600),R=n+600;
set<long long> s;
for(long long i=L;i<=R;i++){
for(long long j=2;j*j<=i;j++){
if(i%j==0){
s.insert(j);
s.insert(i/j);
}
}
}
vector<long long> vx;
for(set<long long>::iterator it=s.begin();it!=s.end();it++){
vx.push_back(*it);
}
sort(all(vx));
FORE(i,0,vx.size()){
if((n-1)%vx[i]==0 && n-1>vx[i])n--;
else if(n%vx[i]==0 && n>vx[i])n++;
}
return n;
}
};