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

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

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