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

「プロジェクトオイラー問い31～40」(2012/12/21 (金) 03:08:33) の最新版変更点

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

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

*問い31
イギリスの硬化を使って２００ペンスを作る方法は何通りか？

解法
動的計画法の練習問題そのもので計算量はたったの１６００回で終わります。
計算回数数億回以下なら１秒以内で答えが出るので何も考えることがありません。

 #include<stdio.h>
 int main(){
	int memo[201]={1,0},coins[8]={1,2,5,10,20,50,100,200};
	for(int i=0;i<8;i++){
		for(int m=0;m+coins[i]<=200;m++){
			memo[m+coins[i]]+=memo[m];
		}
	}
	printf("%d",memo[200]);
 }












*問い32
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2032
すべての桁に 1 から n が一度だけ使われている数をn桁の数が pandigital であるということにしよう: 例えば5桁の数 15234 は 1から5の pandigital である.
7254 は面白い性質を持っている. 39 × 186 = 7254 と書け, 掛けられる数, 掛ける数, 積が1から9の pandigital となる.
掛けられる数/掛ける数/積が1から9の pandigital となるような積の総和を求めよ.
HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.

解法
再帰関数で解いてみましたが何だかコードが綺麗ともいいがたく。
解くだけなら簡単、エレガントに解くのは難しい。
綺麗なコード思いつかないな。
再帰関数でa*bのaとｂを決めて、後はaとｂの桁数とa*bの桁数の合計が９ケタなら条件を満たしているか調べるだけす。
spents配列で使用済みの数字を記録し再帰関数の中で使用済み未使用を判別しながら全探索です。
ｃ++　コード実行時間　0.032秒、普通にループ回した方が早いかも。



 #include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 #include<set>
 #include<time.h>
 bool spents[10]={true};
 std::set<int> memo;
 void saiki(int a,int b,int multA,int multB,int aKeta,int bKeta){
	if(a>b)return;
	char num[30];
	sprintf(num,"%d",a*b);
	int keta=aKeta+bKeta+strlen(num);
	if(keta>9||aKeta>=5||bKeta>=5)return;
	if(keta==9){
		bool oks[10];
		memcpy(oks,spents,sizeof(oks));
		for(int i=0;i<strlen(num);i++){
			if(oks[num[i]-'0']==true)return;
			oks[num[i]-'0']=true;
		}
		memo.insert(a*b);
	}else{
		for(int i=1;i<10;i++){
			if(spents[i]==false){
				spents[i]=true;
				saiki(a+multA*i,b,multA*10,multB,aKeta+1,bKeta);
				saiki(a,b+multB*i,multA,multB*10,aKeta,bKeta+1);
				spents[i]=false;
			}
		}
	}
 }  
 int main(){
	double start=clock();
	for(int i=1;i<10;i++)spents[i]=false;
	saiki(0,0,1,1,0,0);
	int ans=0;
	for(std::set<int>::iterator it=memo.begin();it!=memo.end();it++){
		ans+=(*it);
	}
	printf("%d %lf",ans,clock()-start);
 }




解法２
ループにしてみました。
そんなに速度アップした感じがしません。
いくつか計算してみると分かりますが１桁*４桁＝４桁か２桁*３桁＝４桁のみ考慮すればよいようです。


 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<time.h>
 int main(){
	double start=clock();
	char num[30];
	bool spents[10];
	int oks[10000]={0};
	int ans=0;
	for(int a=1;a<100;a++){
		for(int b=100;b<10000;b++){
			if(a*b>=10000)break;
			sprintf(num,"%d%d%d",a,b,a*b);
			if(strlen(num)==9){
				memset(spents,false,sizeof(spents));
				spents[0]=true;
				bool ok=true;
				for(int i=0;i<9;i++){
					if(spents[num[i]-'0']==true){
						ok=false;
						break;
					}
					spents[num[i]-'0']=true;
				}
				if(ok==true)oks[a*b]=a*b;
			}
		}
	}
	for(int i=1000;i<10000;i++)ans+=oks[i];
	printf("%d %lf",ans,clock()-start);
 }









*問い33
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2033
掟破りの約分法が使える分数をすべて見つけ出せ

解法
簡単な問題ですがコードを短くしようとするとちょっとした難問になります。
コードを短くするには問題の特殊性に着目するしかありません。
検討するのもめんどくさかったので、素朴に定義通り計算して全パタンを検討してみました。

 #include<stdio.h>
 int gcd ( int a, int b ){
	int c;
	while ( a != 0 ) {
		c = a; a = b%a;  b = c;
	}
	return b;
 }
 int main(){
	int m1,m2,ansD=1,ansU;
	for(int a1=10;a1<100;a1++){
		for(int a2=a1+1;a2<100;a2++){
			int k=gcd(a1,a2);
			if(k%10==0||a1%11==0||a2%11==0)continue;
			m1=a1/k;
			m2=a2/k;
			if(a1%10==a2/10){
				int k2=gcd(a1/10,a2%10);
				if((a1/10)/k2==m1&&(a2%10)/k2==m2){
					ansD*=m2;
					ansU*=m1;
					printf("(%d %d)",a1,a2);
				}
			}
			if(a1/10==a2%10){
				int k2=gcd(a1%10,a2/10);
				if((a1%10)/k2==m1&&(a2/10)/k2==m2){
					ansD*=m2;
					ansU*=m1;
					printf("(%d %d)",a1,a2);
				}
			}
		}
	}
	printf("ans=%d",ansD/gcd(ansU,ansD));
 }





*問い34
各桁の階乗の和が元の数と同じになる数の和を求めよ。

解法
文字列になおして足し算していきます。
9,99,999,9999,99999,999999、、がその桁での階乗の和の最大値を与えますが、999999の各桁の階乗の和は2540160となり9999999より小さくなることが分かります。
つまり2540160より大きな数を検討する必要はありません。
なので後は全部チェックするだけです。
条件を満たす数はたった２つしかないので何か手計算か動的計画法でも答えが出そうな気もします。


 #include<stdio.h>
 #include<stdlib.h> 
 int main(){
	int facts[10]={1,1,2,6,24,120,720,5040,40320,362880};
	char num[20];
	int ans=0;
	for(int i=3;i<=2540160;i++){
		sprintf(num,"%d",i);
		int sum=0;
		for(int j=0;num[j]!='\0';j++){
			sum+=facts[num[j]-'0'];
		}
		if(i==sum){
			printf("%d ",i);
			ans+=i;
		}
	}
	printf("\nans=%d",ans);
 }













*問い35
百万以下の巡回素数の数を求めよという問題。

解法
最初に百万以下の素数を全て求めisPrime[m]=mが素数ならtrueを返す配列にセットします。
後は２の場合を最初に答えに足しておいて、後は百万以下の全ての奇数で条件を満たす数をチェックして足していきます。
0を含む素数を巡回すると末尾が0になるので0を含む素数は巡回素数になりません。
これに注意して求めます。


 #include<stdio.h>
 #include<string.h>
 const int up=1000*1000;
 bool isPrime[up+1];
 void setPrime(){
	memset(isPrime,true,sizeof(isPrime));
	isPrime[0]=isPrime[1]=false;
	for(int i=4;i<=up;i+=2)isPrime[i]=false;
	for(int i=3;i<=up;i+=2){
		if(isPrime[i]==false)continue;
		for(int j=i*3;j<=up;j+=2*i)isPrime[j]=false;
	}
 }
 int isAllSlideOk(int n){
	if(isPrime[n]==false)return false;
	int mask=1;
	while(mask<=n){
		if((n/mask)%10==0)return false;//０を含む数をスライドすると末尾の数字が0になるので条件を満たさず
		mask*=10;
	}
	int base=10;
	int num=n;
	while(base<mask){
		num=(num*10)%mask+num/(mask/10);
		if(isPrime[num]==false)return false;
		base*=10;
	}
	return true;
 }
 int main(){
	int ans=1,num;
	setPrime();
	for(int i=3;i<=up;i+=2){
		ans+=isAllSlideOk(i);
	}
	printf("%d",ans);
 }










*問い36
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2036
585 = 10010010012 (2進) は10進でも2進でも回文数である.
100万未満で10進でも2進でも回文数になるような数の総和を求めよ.
(注: 先頭に0を含めて回文にすることは許されない.)

解法
１０進数の回文数だけ生成して後はこれが２進数でも正しいか調べれば計算量が落ちます。
その代わりコードが膨らみました。
もうちょっときれいなコードってなんでしょうね。


 #include<stdio.h>
 int BitRev(int num){
 	int rev=0;
 	for(int b=1;b<=num;b*=2){
 		rev*=2;
 		if((num&b)!=0)rev+=1;
 	}
 	return rev;
 }
 int main(){
 	int ans=0;
 	for(int a=1;a<1000;a++){
 		//2,4,6桁
 		int num,num2;
 		if(a>=100){
 			num=(a/100)+((a/10)%10)*10+(a%10)*100;
 			num2=num+a*1000;
 		}else if(a>=10){
 			num=a/10+(a%10)*10;
 			num2=num+a*100;
 		}else{
 			num=a;
 			num2=num+a*10;
 		}
 		if(num2==BitRev(num2)){
 			ans+=num2;
 			printf("%d ",num2);
 		}
 		//３桁、５桁
 		if(a<100){
 			for(int j=0;j<10;j++){
 				if(a>=10){
 					num2=num+j*100+a*1000;
 				}else{
					num2=num+j*10+a*100;
 				}
 				if(num2==BitRev(num2)){
 					ans+=num2;
 					printf("%d ",num2);
 				}
 			}
 		}
 	}
 	for(int i=1;i<10;i++){
 		if(BitRev(i)==i){
 			ans+=i;
 			printf("%d ",i);//1桁
 		}
 	}
 	printf("\nans=%d",ans);
 }









*問い37
3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).
右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.
注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

解法
小さな数字から生成しようとしたのですが、意外とルールが難しく。
もしかしたら生成に使う記憶用vectorのサイズが１億とか１０億までメモする必要もあるかもしれない。
その危険性を考え素朴に小さい数から全部確かめることにしました。

 #include<stdio.h>
 #include<time.h>
 bool isPrime(int n){
	if(n<2)return false;
	for(int i=2;i*i<=n;i+=(i&1)+1){
		if(n%i==0)return false;
	}
	return true;
 }
 bool check(int n){
	int num=n;
	while(num!=0){
		if(isPrime(num)==false)return false;
		num/=10;
	}
	num=n;
	int mask=1;
	while(mask<=num)mask*=10;
	while(num!=0){
		if(isPrime(num)==false)return false;
		num=((num*10)%mask)/10;
		mask/=10;
	}
	return true;
 }
 int main(){
	int count=0,ans=0;
	double start=clock();
	for(int i=10;count!=11;i++){
		if(check(i)==true){
			printf("(%d %d)\n",count,i);
			count++;
			ans+=i;
		}
	}
	printf("ans=%d time=%lf",ans,clock()-start);
 }












*問い38
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2038
パンデジタル数に関する問題。

解法
これも全部の場合を試してもわずか１０万回の計算量で済みます。
なので手っ取り早くコードを書きました。


 #include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 bool check(char num[30]){
	bool spents[10];
	memset(spents,false,sizeof(spents));
	spents[0]=true;
	for(int i=0;i<9;i++){
		if(spents[num[i]-'0']==true)return false;
		spents[num[i]-'0']=true;
	}
	return true;
 }
 int toInt(char num[30]){
	int re=0;
	for(int i=0;num[i]!='\0';i++){
		re*=10;
		re+=num[i]-'0';
	}
	return re;
 }
 int main(){
	int ans=0;
	for(int a=1;a<=9999;a++){
		char num[30],next[30];
		num[0]='\0';
		for(int i=1;strlen(num)<9;i++){
			sprintf(next,"%s%d",num,a*i);
			memcpy(num,next,sizeof(next));
		}
		int n=toInt(num);
		if(strlen(num)==9&&check(num)==true&&ans<n){
			ans=n;
		}
	}
	printf("ans=%d",ans);
 }











*問い39
辺の長さが {a,b,c} と整数の3つ組である直角三角形を考え, その周囲の長さを p とする. p = 120のときには3つの解が存在する:
{20,48,52}, {24,45,51}, {30,40,50}
p ≤ 1000 のとき解の数が最大になる p はいくつか?

解法
原始ピタゴラス数の公式で条件を満たす周長を求め１倍以上の定数倍をカウントして集計します。
それだけです。

 #include<stdio.h>
 int GCD(int a, int b){
	while( 1 ){
		a = a % b;
		if( a == 0 )return b;
		b = b % a;
		if( b == 0 )return a;
	}
 }
 int main(){
	int memo[1001]={0},ansCount=0,ansLen=0;
	for(int m=2;m*m+1*1+m*m-1*1+2*m*1<=1000;m++){
		for(int n=1;n<m;n++){
			int a=m*m-n*n;
			int b=2*m*n;
			int c=m*m+n*n;
			int l=a+b+c;
			if(l>1000)break;
			if(GCD(n,m)!=1 || (m-n)%2==0)continue;
			while(l<=1000){
				memo[l]++;
				if(memo[l]>ansCount){
					ansCount=memo[l];
					ansLen=l;
				}
				l+=a+b+c;
			}
		}
	}
	printf("ans=%d %d",ansLen,ansCount);
 }

*問い31
イギリスの硬化を使って２００ペンスを作る方法は何通りか？

解法
動的計画法の練習問題そのもので計算量はたったの１６００回で終わります。
計算回数数億回以下なら１秒以内で答えが出るので何も考えることがありません。

 #include<stdio.h>
 int main(){
	int memo[201]={1,0},coins[8]={1,2,5,10,20,50,100,200};
	for(int i=0;i<8;i++){
		for(int m=0;m+coins[i]<=200;m++){
			memo[m+coins[i]]+=memo[m];
		}
	}
	printf("%d",memo[200]);
 }












*問い32
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2032
すべての桁に 1 から n が一度だけ使われている数をn桁の数が pandigital であるということにしよう: 例えば5桁の数 15234 は 1から5の pandigital である.
7254 は面白い性質を持っている. 39 × 186 = 7254 と書け, 掛けられる数, 掛ける数, 積が1から9の pandigital となる.
掛けられる数/掛ける数/積が1から9の pandigital となるような積の総和を求めよ.
HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.

解法
再帰関数で解いてみましたが何だかコードが綺麗ともいいがたく。
解くだけなら簡単、エレガントに解くのは難しい。
綺麗なコード思いつかないな。
再帰関数でa*bのaとｂを決めて、後はaとｂの桁数とa*bの桁数の合計が９ケタなら条件を満たしているか調べるだけす。
spents配列で使用済みの数字を記録し再帰関数の中で使用済み未使用を判別しながら全探索です。
ｃ++　コード実行時間　0.032秒、普通にループ回した方が早いかも。



 #include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 #include<set>
 #include<time.h>
 bool spents[10]={true};
 std::set<int> memo;
 void saiki(int a,int b,int multA,int multB,int aKeta,int bKeta){
	if(a>b)return;
	char num[30];
	sprintf(num,"%d",a*b);
	int keta=aKeta+bKeta+strlen(num);
	if(keta>9||aKeta>=5||bKeta>=5)return;
	if(keta==9){
		bool oks[10];
		memcpy(oks,spents,sizeof(oks));
		for(int i=0;i<strlen(num);i++){
			if(oks[num[i]-'0']==true)return;
			oks[num[i]-'0']=true;
		}
		memo.insert(a*b);
	}else{
		for(int i=1;i<10;i++){
			if(spents[i]==false){
				spents[i]=true;
				saiki(a+multA*i,b,multA*10,multB,aKeta+1,bKeta);
				saiki(a,b+multB*i,multA,multB*10,aKeta,bKeta+1);
				spents[i]=false;
			}
		}
	}
 }  
 int main(){
	double start=clock();
	for(int i=1;i<10;i++)spents[i]=false;
	saiki(0,0,1,1,0,0);
	int ans=0;
	for(std::set<int>::iterator it=memo.begin();it!=memo.end();it++){
		ans+=(*it);
	}
	printf("%d %lf",ans,clock()-start);
 }




解法２
ループにしてみました。
そんなに速度アップした感じがしません。
いくつか計算してみると分かりますが１桁*４桁＝４桁か２桁*３桁＝４桁のみ考慮すればよいようです。


 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<time.h>
 int main(){
	double start=clock();
	char num[30];
	bool spents[10];
	int oks[10000]={0};
	int ans=0;
	for(int a=1;a<100;a++){
		for(int b=100;b<10000;b++){
			if(a*b>=10000)break;
			sprintf(num,"%d%d%d",a,b,a*b);
			if(strlen(num)==9){
				memset(spents,false,sizeof(spents));
				spents[0]=true;
				bool ok=true;
				for(int i=0;i<9;i++){
					if(spents[num[i]-'0']==true){
						ok=false;
						break;
					}
					spents[num[i]-'0']=true;
				}
				if(ok==true)oks[a*b]=a*b;
			}
		}
	}
	for(int i=1000;i<10000;i++)ans+=oks[i];
	printf("%d %lf",ans,clock()-start);
 }









*問い33
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2033
掟破りの約分法が使える分数をすべて見つけ出せ

解法
簡単な問題ですがコードを短くしようとするとちょっとした難問になります。
コードを短くするには問題の特殊性に着目するしかありません。
検討するのもめんどくさかったので、素朴に定義通り計算して全パタンを検討してみました。

 #include<stdio.h>
 int gcd ( int a, int b ){
	int c;
	while ( a != 0 ) {
		c = a; a = b%a;  b = c;
	}
	return b;
 }
 int main(){
	int m1,m2,ansD=1,ansU;
	for(int a1=10;a1<100;a1++){
		for(int a2=a1+1;a2<100;a2++){
			int k=gcd(a1,a2);
			if(k%10==0||a1%11==0||a2%11==0)continue;
			m1=a1/k;
			m2=a2/k;
			if(a1%10==a2/10){
				int k2=gcd(a1/10,a2%10);
				if((a1/10)/k2==m1&&(a2%10)/k2==m2){
					ansD*=m2;
					ansU*=m1;
					printf("(%d %d)",a1,a2);
				}
			}
			if(a1/10==a2%10){
				int k2=gcd(a1%10,a2/10);
				if((a1%10)/k2==m1&&(a2/10)/k2==m2){
					ansD*=m2;
					ansU*=m1;
					printf("(%d %d)",a1,a2);
				}
			}
		}
	}
	printf("ans=%d",ansD/gcd(ansU,ansD));
 }





*問い34
各桁の階乗の和が元の数と同じになる数の和を求めよ。

解法
文字列になおして足し算していきます。
9,99,999,9999,99999,999999、、がその桁での階乗の和の最大値を与えますが、999999の各桁の階乗の和は2540160となり9999999より小さくなることが分かります。
つまり2540160より大きな数を検討する必要はありません。
なので後は全部チェックするだけです。
条件を満たす数はたった２つしかないので何か手計算か動的計画法でも答えが出そうな気もします。


 #include<stdio.h>
 #include<stdlib.h> 
 int main(){
	int facts[10]={1,1,2,6,24,120,720,5040,40320,362880};
	char num[20];
	int ans=0;
	for(int i=3;i<=2540160;i++){
		sprintf(num,"%d",i);
		int sum=0;
		for(int j=0;num[j]!='\0';j++){
			sum+=facts[num[j]-'0'];
		}
		if(i==sum){
			printf("%d ",i);
			ans+=i;
		}
	}
	printf("\nans=%d",ans);
 }













*問い35
百万以下の巡回素数の数を求めよという問題。

解法
最初に百万以下の素数を全て求めisPrime[m]=mが素数ならtrueを返す配列にセットします。
後は２の場合を最初に答えに足しておいて、後は百万以下の全ての奇数で条件を満たす数をチェックして足していきます。
0を含む素数を巡回すると末尾が0になるので0を含む素数は巡回素数になりません。
これに注意して求めます。


 #include<stdio.h>
 #include<string.h>
 const int up=1000*1000;
 bool isPrime[up+1];
 void setPrime(){
	memset(isPrime,true,sizeof(isPrime));
	isPrime[0]=isPrime[1]=false;
	for(int i=4;i<=up;i+=2)isPrime[i]=false;
	for(int i=3;i<=up;i+=2){
		if(isPrime[i]==false)continue;
		for(int j=i*3;j<=up;j+=2*i)isPrime[j]=false;
	}
 }
 int isAllSlideOk(int n){
	if(isPrime[n]==false)return false;
	int mask=1;
	while(mask<=n){
		if((n/mask)%10==0)return false;//０を含む数をスライドすると末尾の数字が0になるので条件を満たさず
		mask*=10;
	}
	int base=10;
	int num=n;
	while(base<mask){
		num=(num*10)%mask+num/(mask/10);
		if(isPrime[num]==false)return false;
		base*=10;
	}
	return true;
 }
 int main(){
	int ans=1,num;
	setPrime();
	for(int i=3;i<=up;i+=2){
		ans+=isAllSlideOk(i);
	}
	printf("%d",ans);
 }










*問い36
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2036
585 = 10010010012 (2進) は10進でも2進でも回文数である.
100万未満で10進でも2進でも回文数になるような数の総和を求めよ.
(注: 先頭に0を含めて回文にすることは許されない.)

解法
１０進数の回文数だけ生成して後はこれが２進数でも正しいか調べれば計算量が落ちます。
その代わりコードが膨らみました。
もうちょっときれいなコードってなんでしょうね。


 #include<stdio.h>
 int BitRev(int num){
 	int rev=0;
 	for(int b=1;b<=num;b*=2){
 		rev*=2;
 		if((num&b)!=0)rev+=1;
 	}
 	return rev;
 }
 int main(){
 	int ans=0;
 	for(int a=1;a<1000;a++){
 		//2,4,6桁
 		int num,num2;
 		if(a>=100){
 			num=(a/100)+((a/10)%10)*10+(a%10)*100;
 			num2=num+a*1000;
 		}else if(a>=10){
 			num=a/10+(a%10)*10;
 			num2=num+a*100;
 		}else{
 			num=a;
 			num2=num+a*10;
 		}
 		if(num2==BitRev(num2)){
 			ans+=num2;
 			printf("%d ",num2);
 		}
 		//３桁、５桁
 		if(a<100){
 			for(int j=0;j<10;j++){
 				if(a>=10){
 					num2=num+j*100+a*1000;
 				}else{
					num2=num+j*10+a*100;
 				}
 				if(num2==BitRev(num2)){
 					ans+=num2;
 					printf("%d ",num2);
 				}
 			}
 		}
 	}
 	for(int i=1;i<10;i++){
 		if(BitRev(i)==i){
 			ans+=i;
 			printf("%d ",i);//1桁
 		}
 	}
 	printf("\nans=%d",ans);
 }









*問い37
3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).
右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.
注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

解法
小さな数字から生成しようとしたのですが、意外とルールが難しく。
もしかしたら生成に使う記憶用vectorのサイズが１億とか１０億までメモする必要もあるかもしれない。
その危険性を考え素朴に小さい数から全部確かめることにしました。

 #include<stdio.h>
 #include<time.h>
 bool isPrime(int n){
	if(n<2)return false;
	for(int i=2;i*i<=n;i+=(i&1)+1){
		if(n%i==0)return false;
	}
	return true;
 }
 bool check(int n){
	int num=n;
	while(num!=0){
		if(isPrime(num)==false)return false;
		num/=10;
	}
	num=n;
	int mask=1;
	while(mask<=num)mask*=10;
	while(num!=0){
		if(isPrime(num)==false)return false;
		num=((num*10)%mask)/10;
		mask/=10;
	}
	return true;
 }
 int main(){
	int count=0,ans=0;
	double start=clock();
	for(int i=10;count!=11;i++){
		if(check(i)==true){
			printf("(%d %d)\n",count,i);
			count++;
			ans+=i;
		}
	}
	printf("ans=%d time=%lf",ans,clock()-start);
 }












*問い38
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2038
パンデジタル数に関する問題。

解法
これも全部の場合を試してもわずか１０万回の計算量で済みます。
なので手っ取り早くコードを書きました。


 #include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 bool check(char num[30]){
	bool spents[10];
	memset(spents,false,sizeof(spents));
	spents[0]=true;
	for(int i=0;i<9;i++){
		if(spents[num[i]-'0']==true)return false;
		spents[num[i]-'0']=true;
	}
	return true;
 }
 int toInt(char num[30]){
	int re=0;
	for(int i=0;num[i]!='\0';i++){
		re*=10;
		re+=num[i]-'0';
	}
	return re;
 }
 int main(){
	int ans=0;
	for(int a=1;a<=9999;a++){
		char num[30],next[30];
		num[0]='\0';
		for(int i=1;strlen(num)<9;i++){
			sprintf(next,"%s%d",num,a*i);
			memcpy(num,next,sizeof(next));
		}
		int n=toInt(num);
		if(strlen(num)==9&&check(num)==true&&ans<n){
			ans=n;
		}
	}
	printf("ans=%d",ans);
 }











*問い39
辺の長さが {a,b,c} と整数の3つ組である直角三角形を考え, その周囲の長さを p とする. p = 120のときには3つの解が存在する:
{20,48,52}, {24,45,51}, {30,40,50}
p ≤ 1000 のとき解の数が最大になる p はいくつか?

解法
原始ピタゴラス数の公式で条件を満たす周長を求め１倍以上の定数倍をカウントして集計します。
それだけです。

 #include<stdio.h>
 int GCD(int a, int b){
	while( 1 ){
		a = a % b;
		if( a == 0 )return b;
		b = b % a;
		if( b == 0 )return a;
	}
 }
 int main(){
	int memo[1001]={0},ansCount=0,ansLen=0;
	for(int m=2;m*m+1*1+m*m-1*1+2*m*1<=1000;m++){
		for(int n=1;n<m;n++){
			int a=m*m-n*n;
			int b=2*m*n;
			int c=m*m+n*n;
			int l=a+b+c;
			if(l>1000)break;
			if(GCD(n,m)!=1 || (m-n)%2==0)continue;
			while(l<=1000){
				memo[l]++;
				if(memo[l]>ansCount){
					ansCount=memo[l];
					ansLen=l;
				}
				l+=a+b+c;
			}
		}
	}
	printf("ans=%d %d",ansLen,ansCount);
 }







*問い40
正の整数を順に連結して得られる以下の10進の無理数を考える:
0.123456789101112131415161718192021...
小数第12位は1である.
dnで小数第n位の数を表す. d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 を求めよ.

解法
一ケタ目の終わりは９文字目、２桁目の終わりは90*2+9文字目、３桁目の終わりは900*3+90*2+9文字目、、。
後はこの数字をつかって何桁目の何個目の数字のどのポイントかを素朴に計算してみました。
もしかしたらこんなめんどくさいことをしなくてもモジュラ演算だけで片がつくかもしれません。


 #include<stdio.h>
 int mod[10]={0,0};
 int base[10]={1};
 int getKeta(int n){
	int p=0;
	while(mod[p+1]<=n-1)p++;
	n=n-mod[p];
	int m=(n-1)/(p+1)+base[p];
	char text[20];
	sprintf(text,"%d",m);
	return text[(n-1)%(p+1)]-'0';
 }
 int main(){
	int b=1,sum=0;
	for(int i=1;i<=6;i++){
		mod[i]=mod[i-1]+9*b*i;
		b*=10;
		base[i]=b;
	}
	int ans=1;
	
	for(int b=1;b<=1000*1000;b*=10){
		ans*=getKeta(b);
	}
	printf("%d",ans);
 }