「オイラープロジェクト131~140」の編集履歴(バックアップ)一覧に戻る

オイラープロジェクト131~140 - (2012/08/30 (木) 05:22:09) の1つ前との変更点

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

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

 *問い132
 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20132
 1111、、、、と無限に続く数字を素数nで割るデスマーチを続けた時、割り算の性質上どこかで循環するか一度割り切れて余り0のインターバルを挟んで次の1が来るかです。
 余り0になったケタではその後同じ周期で111、、、を割れるわけですからこの周期を素数n毎に求めればいいわけです。
 周期が10^9を割り切る値ならそれは素因数となり得ます。
 とりあえず1分ルールを切れなかったけど正答はした。
 1が10^9個並ぶ数11111、、、、、の素因数を小さい方から40個足し合わせるということはクリア。
 どうやって高速化するのだろうか?
 
 このコード実行したらパソコンが悲鳴を上げて冷却ファンがすごい音たてた。
-実行後も全力疾走の後の人間のようにファンの音が鳴りやまない、、、
+実行後も全力疾走の後の人間の呼吸音のようにファンの音が鳴りやまない、、、
 
 
 
 
  #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";
  }