「オイラープロジェクト211～220」の編集履歴（バックアップ）一覧はこちら

「オイラープロジェクト211～220」(2012/12/04 (火) 22:39:04) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*問い214
http://projecteuler.net/problem=214
オイラーのファイ関数を整数ｎに繰り返し適用した時、何回かで１に到達するが２４回の適用で１に到達する素数ｎの合計を答えよ。

解法
この問題逆関数を使えば解けるかと考えました。
宇都宮大学のレポートを参考に逆関数を作って探索してみたところ残念なことに低速でした。
http://uuair.lib.utsunomiya-u.ac.jp/dspace/bitstream/10241/7758/1/30-7-ni.pdf
もしかしたら私の探索の実装が悪かったのかもしれないのでこの手法でリベンジも考えてみます。


単純に全部求めてロックアップの方が早いです。
それでも速度出てないです。
コード実行時間8.346second。
他の人コードを見てもメモリを大量使用で速度を上げるのが基本のようです。
個人的にはもう少し改善してメモリ使用量低で高速か、メモリ使用量をあげてさらなる高速化どちらかですね。

整数論の教育受けたことなし、整数論の本はモノグラフシリーズの整数を読んだことがあるだけというのも何なので整数論の本を一冊購入。
チャレンジ!整数の問題199。
真中まで斜め読みしたが解説が丁寧なので３割程度は分かった感じがする。
これを読み終わったら東大、京大受験ご用達の整数論本もあるらしいのでそれも買っとこう。



 #include<stdio.h>
 #include<vector>
 #include<time.h>
 #include<iostream>
 const int up=4000*10000;
 std::vector<int> sosuu;
 std::vector<bool> so;
 std::vector<int> memo,phi;
 
 void setPrimeAndPhi(){
	so.reserve(up+2);
	phi.reserve(up+2);
	for(int i=0;i<=up+1;i++){
		phi[i]=i;
		so[i]=true;
		if(i>=4&&(i&1)==0){
			phi[i]-=phi[i]/2;
			so[i]=false;
		}
	}
	so[0]=so[1]=false;
	phi[2]=1;
	sosuu.push_back(2);
 	for(int i=3;i<=up+1;i+=2){
		if(so[i]==false)continue;
		if(i<70000)sosuu.push_back(i);
		phi[i]-=phi[i]/i;
		for(int j=i*2;j<=up+1;j+=i){
			so[j]=false;
			phi[j]-=phi[j]/i;
		}
	}
 }
 int main(){
	double start=clock();
	setPrimeAndPhi();
	std::cout<<"point1通過タイム="<<clock()-start<<"\n";
	memo.push_back(0);
	memo.push_back(1);
	int n;
	__int64 ans=0;
 	
	for(int i=2;i<4000*10000;i++){
		int n=phi[i];
		int len=memo[n]+1;
		memo.push_back(len);
		if(n!=i-1)continue;
		if(len==25)ans+=i;
	}
	std::cout<<ans<<" totalTime="<<clock()-start;
 }
　




*問い215

この問題は条件がきついので全探索でも行けるかもしれないと考えたのですが念のためメモ化計算でいってみました。
出てきた数字は&bold(){806844323190414}通りと意外と大きなものでしたが計算は一瞬で終わりました。
左端から全段完璧に仕上げていくという方法を取ることで下から積み上げるより計算量を減らせます。
解法は３分でおもいつきましたが、コードの記述にはめちゃ時間かかりました。
そのかいあってコードはめちゃ高速に動きます。

横から完璧に仕上げていけば計算量が減る。
仮の話ですが単純使い捨て労働者にこの組み合わせ数を求めるのが毎日の自分の仕事といえば、誰でもこの程度の工夫は普通に行うでしょう。
プログラムだと問題が抽象的になるぶんこの程度の素朴な発想でも気付かないときは気付かないものですが。
縦のものを横に、たったこれだけのことです。





 #include<stdio.h>
 #include<map>
 #include<string.h>
 #include<iostream>
 const int h=10;
 const int w=32;
 struct S{
	int cols[3][h+2];//左端から全段煉瓦を積み上げる上段下段に番兵を置く
	int rights[h+2];//今積んでいる位置から右端何個目まで到達しているか
	bool operator<(const S& s)const{
		for(int i=1;i<=h;i++){
			if(cols[0][i]!=s.cols[0][i])return cols[0][i]<s.cols[0][i];
			if(cols[1][i]!=s.cols[1][i])return cols[1][i]<s.cols[1][i];
		}
		return false;
	}
	void rShiftCopy(S& s){
		memcpy(s.cols[0],cols[1],sizeof(cols[1]));
		memcpy(s.cols[1],cols[2],sizeof(cols[2]));
		memset(s.cols[2],0,sizeof(s.cols[2]));
		s.rights[0]=s.rights[h+1]=0;//上段下段の番兵
		for(int i=1;i<=h;i++){
			s.rights[i]=rights[i]-(rights[i]>0);//0以上なら引く
		}
	}
 };
 std::map<S,__int64> memo,next;
 S nextS;
 void saiki(S& s,int deep,int col,__int64 p){
	if(deep<=h){
		if(s.cols[0][deep]==1){
			saiki(s,deep+1,col,p);
		}else{
			if(col+2>w)return ;//右端をはみ出した
			if(s.rights[deep-1]!=2&&s.rights[deep+1]!=2){
				if(col+2==w)s.rights[deep]=-10;//端に到達
				else s.rights[deep]=2;//２つブロック
				
				//上段に２ブロックがないかチェック
				s.cols[0][deep]=s.cols[1][deep]=1;
				s.cols[2][deep]=0;//あり得ないが念のため
				saiki(s,deep+1,col,p);//２つブロックで次へ
				s.cols[0][deep]=s.cols[1][deep]=s.cols[2][deep]=0;
				s.rights[deep]=0;
			}
			if(col+3>w)return ;//右端をはみ出した
			if(s.rights[deep-1]!=3&&s.rights[deep+1]!=3){
				if(deep<h-1&&s.rights[deep+1]==3)return ;//上段に３ブロックが
				if(col+3==w) s.rights[deep]=-10;//端に到達
				else s.rights[deep]=3;//３つブロック
				
				s.cols[0][deep]=s.cols[1][deep]=s.cols[2][deep]=1;
				saiki(s,deep+1,col,p);
				s.cols[0][deep]=s.cols[1][deep]=s.cols[2][deep]=0;
				s.rights[deep]=0;
			}
		}
	}else{
		s.rShiftCopy(nextS);
		if(next.find(nextS)==next.end()){
			next[nextS]=p;
		}else{
			next[nextS]+=p;
		}
	}
 }
 int main(){	
	std::map<S,__int64>::iterator it;
	S s,last,s2;
	__int64 p;
	memset(s.cols,0,sizeof(s.cols));
	memset(s.rights,0,sizeof(s.rights));
	last=s;//最後の集計用
	for(int i=1;i<=h;i++)last.cols[0][i]=1;
	memo[s]=1;
	for(int i=0;i<w-1;i++){
		for(it=memo.begin();it!=memo.end();it++){
			s=(*it).first;
			p=(*it).second;
			saiki(s,1,i,p);
		}
		memo.clear();//ここは計算量より分かりやすさです。
		memo.insert(next.begin(),next.end());
		next.clear();
	}
	std::cout<<memo[last];
 }

*問い211
http://projecteuler.net/problem=211


解法
とりあえず答えを確認するために全部検証してみました。
速度出てないので駄目です。
どうやって答えを導き出すか？
下から組み立てるのだと思いますが思いつかない状態です。



 #include<stdio.h>
 #include<math.h>
 #include<map>
 std::map<__int64,__int64> memo;
 void saiki(__int64 num,__int64& ans,std::map<__int64,__int64>::iterator& it){
	ans+=num;
	if(it==memo.end())return;
	std::map<__int64,__int64>::iterator it2=it;
	it2++;
	for(;it2!=memo.end();it2++){
		__int64 sec=(*it2).second;
		__int64 fir=(*it2).first;
		for(int i=1;i<=sec;i++){
			saiki(num*pow(fir,i),ans,it2);
		}
	}
 }
 bool calc(__int64 n){
	__int64 ans=0;
	memo.clear();
	memo[1]=1;
	for(__int64 i=2;i*i<=n;i+=(i&1)+1){
		int count=0;
		while(n%i==0){
			n/=i;
			count++;
		}
		if(count!=0)memo[i*i]=count;
	}
	if(n!=1){
		if(memo.find(n*n)==memo.end())memo[n*n]=0;
		memo[n*n]++;
	}
	saiki(1,ans,memo.begin());
	__int64 re=sqrt(ans);
	return re*re==ans;
 }
 int main(){
	int limit=64000000;
	//int limit=1000;
	__int64 ans=1;
	for(int i=2;i<limit;i++){
		if(calc(i)==true)ans+=i;
		if(i%100000==0)printf("(%d %lld)",i,ans);
	}
	printf("%lld",ans);
 }



*問い214
http://projecteuler.net/problem=214
オイラーのファイ関数を整数ｎに繰り返し適用した時、何回かで１に到達するが２４回の適用で１に到達する素数ｎの合計を答えよ。

解法
この問題逆関数を使えば解けるかと考えました。
宇都宮大学のレポートを参考に逆関数を作って探索してみたところ残念なことに低速でした。
http://uuair.lib.utsunomiya-u.ac.jp/dspace/bitstream/10241/7758/1/30-7-ni.pdf
もしかしたら私の探索の実装が悪かったのかもしれないのでこの手法でリベンジも考えてみます。


単純に全部求めてロックアップの方が早いです。
それでも速度出てないです。
コード実行時間8.346second。
他の人コードを見てもメモリを大量使用で速度を上げるのが基本のようです。
個人的にはもう少し改善してメモリ使用量低で高速か、メモリ使用量をあげてさらなる高速化どちらかですね。

整数論の教育受けたことなし、整数論の本はモノグラフシリーズの整数を読んだことがあるだけというのも何なので整数論の本を一冊購入。
チャレンジ!整数の問題199。
真中まで斜め読みしたが解説が丁寧なので３割程度は分かった感じがする。
これを読み終わったら東大、京大受験ご用達の整数論本もあるらしいのでそれも買っとこう。



 #include<stdio.h>
 #include<vector>
 #include<time.h>
 #include<iostream>
 const int up=4000*10000;
 std::vector<int> sosuu;
 std::vector<bool> so;
 std::vector<int> memo,phi;
 
 void setPrimeAndPhi(){
	so.reserve(up+2);
	phi.reserve(up+2);
	for(int i=0;i<=up+1;i++){
		phi[i]=i;
		so[i]=true;
		if(i>=4&&(i&1)==0){
			phi[i]-=phi[i]/2;
			so[i]=false;
		}
	}
	so[0]=so[1]=false;
	phi[2]=1;
	sosuu.push_back(2);
 	for(int i=3;i<=up+1;i+=2){
		if(so[i]==false)continue;
		if(i<70000)sosuu.push_back(i);
		phi[i]-=phi[i]/i;
		for(int j=i*2;j<=up+1;j+=i){
			so[j]=false;
			phi[j]-=phi[j]/i;
		}
	}
 }
 int main(){
	double start=clock();
	setPrimeAndPhi();
	std::cout<<"point1通過タイム="<<clock()-start<<"\n";
	memo.push_back(0);
	memo.push_back(1);
	int n;
	__int64 ans=0;
 	
	for(int i=2;i<4000*10000;i++){
		int n=phi[i];
		int len=memo[n]+1;
		memo.push_back(len);
		if(n!=i-1)continue;
		if(len==25)ans+=i;
	}
	std::cout<<ans<<" totalTime="<<clock()-start;
 }
　




*問い215

この問題は条件がきついので全探索でも行けるかもしれないと考えたのですが念のためメモ化計算でいってみました。
出てきた数字は&bold(){806844323190414}通りと意外と大きなものでしたが計算は一瞬で終わりました。
左端から全段完璧に仕上げていくという方法を取ることで下から積み上げるより計算量を減らせます。
解法は３分でおもいつきましたが、コードの記述にはめちゃ時間かかりました。
そのかいあってコードはめちゃ高速に動きます。

横から完璧に仕上げていけば計算量が減る。
仮の話ですが単純使い捨て労働者にこの組み合わせ数を求めるのが毎日の自分の仕事といえば、誰でもこの程度の工夫は普通に行うでしょう。
プログラムだと問題が抽象的になるぶんこの程度の素朴な発想でも気付かないときは気付かないものですが。
縦のものを横に、たったこれだけのことです。





 #include<stdio.h>
 #include<map>
 #include<string.h>
 #include<iostream>
 const int h=10;
 const int w=32;
 struct S{
	int cols[3][h+2];//左端から全段煉瓦を積み上げる上段下段に番兵を置く
	int rights[h+2];//今積んでいる位置から右端何個目まで到達しているか
	bool operator<(const S& s)const{
		for(int i=1;i<=h;i++){
			if(cols[0][i]!=s.cols[0][i])return cols[0][i]<s.cols[0][i];
			if(cols[1][i]!=s.cols[1][i])return cols[1][i]<s.cols[1][i];
		}
		return false;
	}
	void rShiftCopy(S& s){
		memcpy(s.cols[0],cols[1],sizeof(cols[1]));
		memcpy(s.cols[1],cols[2],sizeof(cols[2]));
		memset(s.cols[2],0,sizeof(s.cols[2]));
		s.rights[0]=s.rights[h+1]=0;//上段下段の番兵
		for(int i=1;i<=h;i++){
			s.rights[i]=rights[i]-(rights[i]>0);//0以上なら引く
		}
	}
 };
 std::map<S,__int64> memo,next;
 S nextS;
 void saiki(S& s,int deep,int col,__int64 p){
	if(deep<=h){
		if(s.cols[0][deep]==1){
			saiki(s,deep+1,col,p);
		}else{
			if(col+2>w)return ;//右端をはみ出した
			if(s.rights[deep-1]!=2&&s.rights[deep+1]!=2){
				if(col+2==w)s.rights[deep]=-10;//端に到達
				else s.rights[deep]=2;//２つブロック
				
				//上段に２ブロックがないかチェック
				s.cols[0][deep]=s.cols[1][deep]=1;
				s.cols[2][deep]=0;//あり得ないが念のため
				saiki(s,deep+1,col,p);//２つブロックで次へ
				s.cols[0][deep]=s.cols[1][deep]=s.cols[2][deep]=0;
				s.rights[deep]=0;
			}
			if(col+3>w)return ;//右端をはみ出した
			if(s.rights[deep-1]!=3&&s.rights[deep+1]!=3){
				if(deep<h-1&&s.rights[deep+1]==3)return ;//上段に３ブロックが
				if(col+3==w) s.rights[deep]=-10;//端に到達
				else s.rights[deep]=3;//３つブロック
				
				s.cols[0][deep]=s.cols[1][deep]=s.cols[2][deep]=1;
				saiki(s,deep+1,col,p);
				s.cols[0][deep]=s.cols[1][deep]=s.cols[2][deep]=0;
				s.rights[deep]=0;
			}
		}
	}else{
		s.rShiftCopy(nextS);
		if(next.find(nextS)==next.end()){
			next[nextS]=p;
		}else{
			next[nextS]+=p;
		}
	}
 }
 int main(){	
	std::map<S,__int64>::iterator it;
	S s,last,s2;
	__int64 p;
	memset(s.cols,0,sizeof(s.cols));
	memset(s.rights,0,sizeof(s.rights));
	last=s;//最後の集計用
	for(int i=1;i<=h;i++)last.cols[0][i]=1;
	memo[s]=1;
	for(int i=0;i<w-1;i++){
		for(it=memo.begin();it!=memo.end();it++){
			s=(*it).first;
			p=(*it).second;
			saiki(s,1,i,p);
		}
		memo.clear();//ここは計算量より分かりやすさです。
		memo.insert(next.begin(),next.end());
		next.clear();
	}
	std::cout<<memo[last];
 }