「プロジェクトオイラー問１１０」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問１１０ - (2014/03/07 (金) 04:43:20) の編集履歴(バックアップ)

---

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=２＾３*３＾２はn1=２＾２*３＾３よりも小さい数でより多くの1/x+1/y=1/nのｘｙを持ちます。
これを利用して計算すると探索範囲を大幅に削減できます。

計算量はＢｉｇＯ（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";
}