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

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

オイラープロジェクト131~140 - (2012/08/30 (木) 07:42:38) の編集履歴(バックアップ)


問い132

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

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";
}