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

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

プロジェクトオイラー問110 - (2014/03/07 (金) 04:43:55) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20110

*Problem 110 「ディオファントス逆数 その2」 †
次の等式で x, y, n は正の整数である.

1/x + 1/y = 1/n

n = 1260 では 113 の異なる解があり, この n が解の個数が 100 を超える最小の値である.

解の数が 4,000,000 を超える最小の n を求めよ.

注: この問題は Problem 108 を非常に難しくしたケースである. 総当り法で解ける範囲を超えているので, 賢い解き方が求められる.


解法
問108では私は約数から答えを探しました。
今回は約数から元の数を生成する方法で解きます。
n=2^3*3^2はn1=2^2*3^3よりも小さい数でより多くの1/x+1/y=1/nのxyを持ちます。
これを利用して計算すると探索範囲を大幅に削減できます。

計算量はBigO(17398)でした。
たぶん正当な方法はデファイントス方程式を解くのだと思います。

 #include<stdio.h>
 #include<vector>
 #include<queue>
 #include<iostream>
 
 
 const __int64 primes[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
  
 struct E{
 	__int64 num,perm;
 	std::vector<__int64> counts;
 	int lastPoint;
 	bool operator<(const E& e)const{
 		return num>e.num;
 	}
 	void addPrime(int point){
 		__int64 p1=primes[point];
 		if(counts.size()==point){
 			counts.push_back(3);
 			num*=p1;
 			perm*=3;
 		}else{
 			num*=p1;
 			perm=(perm/counts[point])*(counts[point]+2);
 			counts[point]+=2;
 		}
 		lastPoint=point;
 	}
 };
  
 int main(){
 	E e1,e2;
 	e1.num=2;
 	e1.perm=3;
 	e1.counts.push_back(3);
 	e1.lastPoint=0;
 	std::priority_queue<E> pq;
 	pq.push(e1);
 	int bigO=0;
 	while(!pq.empty()){
 		e1=pq.top();
 		pq.pop();
 		bigO++;
 		if(e1.perm/2+1>400*10000)break;
 		for(int i=e1.lastPoint;i<=e1.counts.size();i++){
 			e2=e1;
 			e2.addPrime(i);
 			if(e2.counts[i-1]<e2.counts[i])continue;
 			pq.push(e2);
 		}
 	}
 	std::cout<<e1.perm/2+1<<" ans="<<e1.num;
 	std::cout<<" BigO"<<bigO<<"\n";
 }