プロジェクトオイラー問142 - sinapusu2002 @ ウィキ

https://projecteuler.net/problem=142
x + y, x − y, x + z, x − z, y + z, y − zが全て平方数になるｘ、ｙ、ｚの組で
ｘ+ｙ+ｚの最も小さいものを計算せよ。

小さいほうから生成する手法を思いつかなかったので上限を適当に定めて上限を少しずつ増やしながら探索しました。
結果計算時間１分となりました。

x-y=a^2
y-z=b^2
x-z=c^2
(x-y)+(y-z)=(x-z)
a^2+b^2=c^2
とみれば原始ピタゴラス数とその定数倍です。
式のうち３つを確定できたわけです。
6つある式をどこまで確定できるかで計算量の減り方がけた違いに減ります。
後はこの条件下での検討をx+y+zが小さいほうから順序集合で生成する方法を思いつければよかったのですが。

#include<stdio.h>
#include<map>
#include<vector>
#include<iostream>
#include<set>
#include<queue>
int 
gcd ( int a, int b )
{
 int c;
 while ( a != 0 ) {
    c = a; a = b%a;  b = c;
  }
  return b;
}

struct E{
	int m,n,k,t,z;
	//t=0ならy-zが(m^2-n^2)^2
	//t=1ならy-zが(2mn)^2
	int getX()const{
		return z+(m*m+n*n)*(m*m+n*n)*k*k;
	}
	int getY()const{
		if(t==0){
			return z+(m*m-n*n)*(m*m-n*n)*k*k;
		}else{
			return z+4*m*m*n*n*k*k;
		}
	}
	
	int sum()const{
		int x=getX();
		int y=getY();
		return (x+y+z);
	}
	bool operator<(const E& e1)const{
		return sum()<e1.sum();
	}
}; 

const int LIMIT=1200*1000;
 
int main(){
	std::set<int> ss;
	for(int i=1;i<40000;i++){
		ss.insert(i*i);
	}
	
 	std::vector<E> vec;
	E e1;
	e1.z=1;
	for(int t=0;t<=1;t++){
		e1.t=t;
		for(int m=2;m<=50;m++){
			e1.m=m;
			for(int n=1;n<m;n++){
				e1.n=n;
				e1.k=1;
 				if(e1.sum()>LIMIT)break;
				if((m-n)%2!=1)continue;
				if(gcd(m,n)!=1)continue;
				for(int k=1;;k++){
 					e1.k=k;
					if(e1.sum()>LIMIT)break;
					vec.push_back(e1);
				}
			}
 		}
	}
	std::sort(vec.begin(),vec.end());
	
	int ans=0;
 	for(int z=1;z*3<=LIMIT;z++){
		if(ans>0&&ans<=z*3)break;
		if(z%1000==0)printf("%d\n",z);
 		for(int i=0;i<vec.size();i++){
			E e1=vec[i];
			e1.z=z;
			if(ans>0&&ans<e1.sum())break;
			int x=e1.getX();
			int y=e1.getY();
 			if(ss.find(x+y)==ss.end())continue;
			if(ss.find(x+z)==ss.end())continue;
			if(ss.find(y+z)==ss.end())continue;
			if((ans==0)||(ans>e1.sum()))ans=e1.sum();
			printf("%d ",ans);
		}
	}
	printf("\nans=%d\n",ans);
}