※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「プロジェクトオイラー問124」の編集履歴(バックアップ)一覧に戻る
プロジェクトオイラー問124」を以下のとおり復元します。
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20124
http://projecteuler.net/problem=124


*Problem 124 「順序付き根基」 †
n の"根基"(radical)は, rad(n) に関する問題。
詳細はリンク先参照のこと。


解法
エラトステネスの篩もどきでテーブル化して計算しソートし1万個めを求めるだけです。
計算量BigO(366401)+10万個の要素のソート。
まあ普通です。



 #include<stdio.h>
 #include<algorithm>
 
 struct E{
 	int n,rad;
 	bool operator<(const E& e)const{
 		if(rad!=e.rad)return rad<e.rad;
 		return n<e.n;
 	}
 };
 const int LIMIT=100000;
 int main(){
 	E rads[LIMIT+1];
 	int bigO=0;
 	for(int i=0;i<=LIMIT;i++){
  		rads[i].n=i;
 		rads[i].rad=1;
 		bigO++;
 	}
 	for(int i=2;i<=LIMIT;i++){
 		if(rads[i].rad>1)continue;
 		for(int j=i;j<=LIMIT;j+=i){
  			bigO++;
 			rads[j].rad*=i;
 		}
 	}
 	std::sort(rads,rads+LIMIT+1);
 	printf("ans=%d BigO=%d\n",rads[10000].n,bigO);
 }

復元してよろしいですか?