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

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

Problem 86 「直方体のルート」 †
下に示す直方体は寸法が6×5×3である. この直方体の1つの頂点Sにクモがいる. また反対の頂点Fにはハエがいる. SからFまでの壁に沿って直線移動する最短ルートは図に示す通りで, この長さは10である.

図略

この最短ルートの候補は3本あるが, 最短のものがいつも整数長さとは限らない.

さて, M×M×M以下の寸法の直方体について, 最短ルートが整数である直方体の数を考える. M=100のとき, 条件を満たす直方体は2060個ある. このM=100は個数が2000を超える最小のMである. なお, M=99のときは1975個である.

100万個を超える最小のMを求めよ.
図などの詳細についてはリンク先参照のこと。

解法
直方体の三辺をa,b,cとしa<=b<=cとしても一般性は失わない。
最短ルートは(a+b)^2+c^2で与えられる。
A a^2+b^2+c^2+2ab
他の組み合わせだと
B a^2+b^2+c^2+2ac
C a^2+b^2+c^2+2bc
他の場合Ｃを最長辺としたときより移動ルートは長くなる。
よって最短ルートは縦横(a+b)、ｃの直角三角形の斜辺が整数になる場合だからこれは原始ピタゴラス数とその整数倍である。

原始ピタゴラス数とその整数倍を辺ｃが短いものから生成されるようにコードを書いては見た。
高速だしメモリもそんなに食ってはないが、複雑なだけでどうもあまりうれしくない。

この問題は他の人のコードを参考にしたほうがよい。
良い方法は適当に上限を定めてその上限までの原始ピタゴラス数を求め、ｃにたいする可能なa,bの組み合わせ数を求める。
後はその整数倍を計算していけばよい。

#include<stdio.h>
#include<queue>
#include<vector>

int gcd ( int a, int b )
{
 int c;
 while ( a != 0 ) {
     c = a; a = b%a;  b = c;
  }
  return b;
}
 
struct MN{
	int m,n,len,addN,k;
	bool operator<(const MN& mn)const{
		return len>mn.len;
	}
	void setMN1(int m1,int n1,int addN1,int k1){
		len=2*m1*n1*k1;
		addN=addN1;
		k=k1;
		m=m1;
		n=n1;
	}
	void setMN2(int m1,int n1,int addN1,int k1){
	len=(m1*m1-n1*n1)*k1;
		addN=addN1;
		k=k1;
 		m=m1;
		n=n1;
	}

	bool setMN_W(int m1,int n1,int addN1,int k1){
 		if(m1<=n1||n1<0)return false;
		if(addN1==1){
			setMN1(m1,n1,addN1,k1);
		}else if(addN1==-1){
			setMN2(m1,n1,addN1,k1);
		}
		return true;
	}

	bool countOK(){
		if(m>n&&n>0&&(m-n)%2==1&&gcd(m,n)==1){
			return true;
		}
		return false;
	}
	int countAdd(){
		int t;
		if(addN==1){
			t = (m*m-n*n)*k;
 		}else{
			t = (2*m*n)*k;
		}
		if(t<len){
			return t/2;
		}
		int t1= t/2-(t-len)+1;
		t1=t1>0?t1:0;
		return t1;
	}
};
 
int main(){
	MN mn,mn1;
	
	std::priority_queue<MN> pq;
	mn.setMN_W(2,1,1,1);
	pq.push(mn);
	mn.setMN_W(2,1,-1,1);
	pq.push(mn);

	
	int count=0,M=1;
	while(count<1000*1000){
		if(pq.top().len>M){
			M=pq.top().len;
		}
		
		while(pq.top().len==M){
			mn=pq.top();
			pq.pop();
			if(mn.n>=mn.m)continue;
			if(mn.countOK()==true){
				count+=mn.countAdd();
 				if(mn1.setMN_W(mn.m, mn.n, mn.addN, mn.k+1)){
					pq.push(mn1);
				}
			}
			if(mn.n==1&&mn.addN==1 && mn.k==1){
				if(mn1.setMN_W(mn.m+1, 1, 1,  1)){
					pq.push(mn1);
				}
			}
			if(mn.n+1==mn.m && mn.addN==-1 && mn.k==1){
				if(mn1.setMN_W(mn.m+1, mn.m, -1, 1)){
					pq.push(mn1);
				}
			}
			
 			if(mn.k==1&&mn1.setMN_W(mn.m, mn.n+mn.addN, mn.addN, mn.k)){
				pq.push(mn1);
			}
		}
	}
	printf("\n(ans=%d)\n",M);
}