プロジェクトオイラー問１１０ - c21coterie @ ウィキ

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