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

「オイラープロジェクト131～140」(2012/09/12 (水) 11:57:07) の最新版変更点

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

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

*問い132
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20132
1111,,,と1が１０億個並んだ数の素因数分解を行ったとき小さいほうから４０個目までの素因数の和を答えよという問題。

1１１１、、、、と無限に続く数字を素数ｎで割るデスマーチを続けた時、割り算の性質上どこかで循環するか一度割り切れて余り0のインターバルを挟んで次の1が来るかです。
余り0になったケタではその後同じ周期で111、、、を割れるわけですからこの周期を素数ｎ毎に求めればいいわけです。
周期が10＾9を割り切る値ならそれは素因数となり得ます。
とりあえず１分ルールを切れなかったけど正答はした。
1が10＾9個並ぶ数11111、、、、、の素因数を小さい方から４０個足し合わせるということはクリア。
しかしこの問題どうやって高速化するのだろうか？

ちなみにこのコード実行したらパソコンが悲鳴を上げて冷却ファンがすごい音たてた。
数分間のコード実行後も全力疾走の後の人間の呼吸音のようにファンの音が鳴りやまない、、、




 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<set>
 #include<iostream>
 #include<math.h>
 const int up=1000000;
 std::vector<__int64> sosuu;
 bool so[up];
 int nummax;
 std::set<__int64> memo;
 void setSo(){
	int i2;
	memset(so,true,sizeof(so));
	sosuu.push_back(2);
	for(int i=3;i<=up;i+=2){
		if(so[i]==false)continue;
		sosuu.push_back(i);
		i2=i*2;
		for(int j=i*3;j<up;j+=i2){
			so[j]=false;
		}
	}
 }
 int calc(__int64 n,__int64 m){
	__int64 t;
	int ans=0;
	while(1){
		t=n%m;
		ans++;
		if(t==0)return ans;
		if(memo.find(t)!=memo.end())return -1;
		memo.insert(t);
		n=t*10+1;
		//if(ans>nummax)return -1;
	}
 }
 int main(){
	setSo();
	__int64 ans=0,count=0,ten=1;
	for(int i=0;i<9;i++)ten*=10;
	//nummax=sqrt(ten);
	std::cout<<sosuu.size()<<" "<<ten<<"\n";
	for(int i=0;i<sosuu.size();i++){
		memo.clear();
		//std::cout<<i<<" "<<sosuu[i];
		int d=calc(1,sosuu[i]);
		//std::cout<<sosuu[i]<<" "<<d<<"\n";
		if(d>0&&ten%d==0){
			count++;
			ans+=sosuu[i];
			std::cout<<"("<<count<<" "<<sosuu[i]<<")\n";
			if(count>=40)break;
		}
	}
	std::cout<<ans<<"\n";
 }


*問い134
連続する素数 p1 = 19, p2 = 23 について考える。1219 は末尾の桁が p1 からなり p2 で割り切られる最小の数であることが確かめられる。
実際、 p1 = 3, p2 = 5 を除けば、全ての p2 > p1 なる連続する素数のペアについて、末尾の桁が p1 からなり p2 で割り切られる数 n が存在する。S を n の最小のものであるとする。
5 ≤ p1 ≤ 1000000 を満たす連続する素数のペア全てに対し ∑ S を求めよ。

２０分もかかって正しい答えを出す最悪のコード。
こんなに時間がかかっては解けてないと同義。
(ax)%b=cを高速に解く方法が分かれば早くなるんだけど、、、


 #include<stdio.h>
 #include<vector>
 #include<iostream>
 #include <windows.h> 
 const int up=1000004;//最後のp2が100万を超える場合を忘れずに
 //const int up =200;
 std::vector<int> sosuu;
 bool so[up+1];
 void setSo(){
	int i2;
	memset(so,true,sizeof(so));
	for(int i=3;i<=up;i+=2){
		if(so[i]==false)continue;
		if(i>3)sosuu.push_back(i);
		i2=i*2;
		for(int j=i*3;j<up;j+=i2){
			so[j]=false;
		}
	}
 }
 __int64 gcd ( __int64 a, __int64 b )
 {
  __int64 c;
  while ( a != 0 ) {
     c = a; a = b%a;  b = c;
  }
  return b;
 } 
 __int64 calc(__int64 p1,__int64 p2){
	__int64 base=1,m,a,b,c;
	while(base<=p1)base*=10;
	m=base%p2;
	a=0;
	b=p2-p1;
	c=gcd(b,m)*p2;
	while((a+b)%m!=0){
		a+=c;
	}
	return (a+b)/m*base+p1;
 }
 int main(){
	setSo();
	__int64 ans=0,t;
	for(int i=0;i<sosuu.size()-1;i++){
		t=calc(sosuu[i],sosuu[i+1]);
		std::cout<<sosuu[i]<<" "<<t<<" "<<t%sosuu[i+1]<<"\n";
		ans+=t;
		if(i%1000==0)Sleep(500);
	}
	std::cout<<"ans="<<ans;
 }




*問い135
正の整数x, y, z が等差数列として与えられたとき、x2 - y2 - z2 = n がちょうど2個の解を持つような最小の正の整数 n は、n = 27である。
342 − 272 − 202 = 122 − 92 − 62 = 27
n = 1155 は、方程式がちょうど10個の解を持つ最小の値である。
ちょうど10個の解を持つような n は、100万までにいくつ存在するか?

x,y,zが等差数列なので(y+a)^2-y^2-(y-a)^2=nとして式変形しn=y(4a-y)を得ます。
後はaとｙがｎの範囲の条件を満たす範囲で全探索すれば答えが出ます。

 #include<stdio.h>
 #include<iostream>
 const int up=1000000;
 //const int up=1200;
 __int64 memo[up+1]={0};
 int main(){
	__int64 a=1,y,b,t;
	while(1){
		b=a*4;
		if(1*(b-1)>up)break;
		for(y=1;y<=2*a;y++){
			t=y*(b-y);
			if(t>up)break;
			if(t<1)continue;
			memo[(int)t]++;
			if(y!=b-y&&y>a)memo[(int)t]++;
		}
		a++;
	}
	int ans=0;
	for(int i=1;i<=up;i++){
		if(memo[i]==10){
			std::cout<<i<<" "<<memo[i]<<"\n";
			ans++;
		}
	}
	std::cout<<ans;
 }

*問い132
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20132
1111,,,と1が１０億個並んだ数の素因数分解を行ったとき小さいほうから４０個目までの素因数の和を答えよという問題。

1１１１、、、、と無限に続く数字を素数ｎで割るデスマーチを続けた時、割り算の性質上どこかで循環するか一度割り切れて余り0のインターバルを挟んで次の1が来るかです。
余り0になったケタではその後同じ周期で111、、、を割れるわけですからこの周期を素数ｎ毎に求めればいいわけです。
周期が10＾9を割り切る値ならそれは素因数となり得ます。
とりあえず１分ルールを切れなかったけど正答はした。
1が10＾9個並ぶ数11111、、、、、の素因数を小さい方から４０個足し合わせるということはクリア。
しかしこの問題どうやって高速化するのだろうか？

ちなみにこのコード実行したらパソコンが悲鳴を上げて冷却ファンがすごい音たてた。
数分間のコード実行後も全力疾走の後の人間の呼吸音のようにファンの音が鳴りやまない、、、




 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<set>
 #include<iostream>
 #include<math.h>
 const int up=1000000;
 std::vector<__int64> sosuu;
 bool so[up];
 int nummax;
 std::set<__int64> memo;
 void setSo(){
	int i2;
	memset(so,true,sizeof(so));
	sosuu.push_back(2);
	for(int i=3;i<=up;i+=2){
		if(so[i]==false)continue;
		sosuu.push_back(i);
		i2=i*2;
		for(int j=i*3;j<up;j+=i2){
			so[j]=false;
		}
	}
 }
 int calc(__int64 n,__int64 m){
	__int64 t;
	int ans=0;
	while(1){
		t=n%m;
		ans++;
		if(t==0)return ans;
		if(memo.find(t)!=memo.end())return -1;
		memo.insert(t);
		n=t*10+1;
		//if(ans>nummax)return -1;
	}
 }
 int main(){
	setSo();
	__int64 ans=0,count=0,ten=1;
	for(int i=0;i<9;i++)ten*=10;
	//nummax=sqrt(ten);
	std::cout<<sosuu.size()<<" "<<ten<<"\n";
	for(int i=0;i<sosuu.size();i++){
		memo.clear();
		//std::cout<<i<<" "<<sosuu[i];
		int d=calc(1,sosuu[i]);
		//std::cout<<sosuu[i]<<" "<<d<<"\n";
		if(d>0&&ten%d==0){
			count++;
			ans+=sosuu[i];
			std::cout<<"("<<count<<" "<<sosuu[i]<<")\n";
			if(count>=40)break;
		}
	}
	std::cout<<ans<<"\n";
 }


*問い134
連続する素数 p1 = 19, p2 = 23 について考える。1219 は末尾の桁が p1 からなり p2 で割り切られる最小の数であることが確かめられる。
実際、 p1 = 3, p2 = 5 を除けば、全ての p2 > p1 なる連続する素数のペアについて、末尾の桁が p1 からなり p2 で割り切られる数 n が存在する。S を n の最小のものであるとする。
5 ≤ p1 ≤ 1000000 を満たす連続する素数のペア全てに対し ∑ S を求めよ。

２０分もかかって正しい答えを出す最悪のコード。
こんなに時間がかかっては解けてないと同義。
(ax)%b=cを高速に解く方法が分かれば早くなるんだけど、、、


 #include<stdio.h>
 #include<vector>
 #include<iostream>
 #include <windows.h> 
 const int up=1000004;//最後のp2が100万を超える場合を忘れずに
 //const int up =200;
 std::vector<int> sosuu;
 bool so[up+1];
 void setSo(){
	int i2;
	memset(so,true,sizeof(so));
	for(int i=3;i<=up;i+=2){
		if(so[i]==false)continue;
		if(i>3)sosuu.push_back(i);
		i2=i*2;
		for(int j=i*3;j<up;j+=i2){
			so[j]=false;
		}
	}
 }
 __int64 gcd ( __int64 a, __int64 b )
 {
  __int64 c;
  while ( a != 0 ) {
     c = a; a = b%a;  b = c;
  }
  return b;
 } 
 __int64 calc(__int64 p1,__int64 p2){
	__int64 base=1,m,a,b,c;
	while(base<=p1)base*=10;
	m=base%p2;
	a=0;
	b=p2-p1;
	c=gcd(b,m)*p2;
	while((a+b)%m!=0){
		a+=c;
	}
	return (a+b)/m*base+p1;
 }
 int main(){
	setSo();
	__int64 ans=0,t;
	for(int i=0;i<sosuu.size()-1;i++){
		t=calc(sosuu[i],sosuu[i+1]);
		std::cout<<sosuu[i]<<" "<<t<<" "<<t%sosuu[i+1]<<"\n";
		ans+=t;
		if(i%1000==0)Sleep(500);
	}
	std::cout<<"ans="<<ans;
 }




*問い135
正の整数x, y, z が等差数列として与えられたとき、x2 - y2 - z2 = n がちょうど2個の解を持つような最小の正の整数 n は、n = 27である。
342 − 272 − 202 = 122 − 92 − 62 = 27
n = 1155 は、方程式がちょうど10個の解を持つ最小の値である。
ちょうど10個の解を持つような n は、100万までにいくつ存在するか?

x,y,zが等差数列なので(y+a)^2-y^2-(y-a)^2=nとして式変形しn=y(4a-y)を得ます。
後はaとｙがｎの範囲の条件を満たす範囲で全探索すれば答えが出ます。

 #include<stdio.h>
 #include<iostream>
 const int up=1000000;
 //const int up=1200;
 __int64 memo[up+1]={0};
 int main(){
	__int64 a=1,y,b,t;
	while(1){
		b=a*4;
		if(1*(b-1)>up)break;
		for(y=1;y<=2*a;y++){
			t=y*(b-y);
			if(t>up)break;
			if(t<1)continue;
			memo[(int)t]++;
			if(y!=b-y&&y>a)memo[(int)t]++;
		}
		a++;
	}
	int ans=0;
	for(int i=1;i<=up;i++){
		if(memo[i]==10){
			std::cout<<i<<" "<<memo[i]<<"\n";
			ans++;
		}
	}
	std::cout<<ans;
 }




*問い138
底の長さbが16, 脚の長さLが17の二等辺三角形を考える.
ピタゴラスの定理より, 三角形の高さh = √(172 − 82) = 15となる. 高さは底の長さより1だけ短い.
b = 272, L = 305とすると, h = 273となり, これは底の長さより1だけ長い. この三角形はh = b ± 1という性質を持つ二等辺三角形の中で二番目に小さい.
h = b ± 1, b, Lが全て正の整数であるとし, そのような二等辺三角形の中で小さい順に12個取ったときの∑Lを求めよ.

式変形しても賢い方法を思いつかなかったので全探索して数列を眺めていたら単純な漸化式を発見。
２次方程式を介した方法だとよほど工夫しないと桁あふれする可能性があったのでよかったよかった。
そのまま解く。

 #include<stdio.h>
 #include<iostream>
 int main(){
	__int64 ans=17,a=17,b[13]={0,16,0},c,d;
	for(int i=1;i<12;i++){
		c=a+b[i];
		a=a*17+b[i]+b[i-1];
		b[i+1]=a-c;
		std::cout<<a<<" "<<b[i+1]<<" ""\n";
		ans+=a;
	}
	std::cout<<ans;
 }