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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2086
整数比の直方体の２点を最短線分でつなげたとき線分の長さが整数になるときがある。
直方体の最大辺をｍとしたとき
ｍ＜＝Mで直方体の種類が１００万通りを超す最小のMを求めよ。

普通に求めてもあれなのでこの問題遊んでみました。
100000<=Mの場合何個の直方体が条件を満たすかで調べてみました。
計算時間３秒。
ans=4487105091
MaxPriorityQueueSize338630
あってるかどうかは少し自信がありません。
プロジェクトオイラーでは私は遅いほうです、一番早い人速すぎ。
俺より１００倍位速いんじゃないか？

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<iostream>


const int LIMIT=100000;
std::map<int,int> down,up;

__int64 gcd ( __int64 a, __int64 b )
{
  	__int64 c;
 	while ( a != 0 ) {
  		 c = a; a = b%a;  b = c;
  	}
	return b;
}

struct E{
	__int64 m,n,a,b,addA,addB,q,addN;
	bool operator<(const E& e)const{
		return b>e.b;
	}
 	void setMN_Big(__int64 m1,__int64 n1,__int64 q1,int addN1){
		m=m1;
		n=n1;
		q=q1;
	addN=addN1;
 		__int64 a1=(m*m-n*n)*q;
		__int64 b1=2*m*n*q;
		a=std::max(a1,b1);
		b=std::min(a1,b1);
		addA=b/2;
		if(a<2*b){
			addB=(b-(a-b))/2+1;
		}else{
			addB=0;
		}
	}
	__int64 nextN(){
		__int64 tN=n;
		if(q>1)return -1;
		while(tN>0&&tN<m){
			tN+=addN;
 			if(addN==2&&up[m]<=tN){
				return -1;
			}else if(addN==-2&&down[m]>=tN){
				return -1;
			}
			if((m-tN)%2==1&&gcd(m,tN)==1){
				return tN;
			}
		}
		return -1;
	}
};


 
int main(){
//200 4713 4321 9034
	__int64 ansA=0,ansB=0,addACount=0,addBCount=0;
	__int64 dellB=0;
	__int64 all=0;
	E e1,e2;
	
	
	
	std::priority_queue<E> pq;
	e1.setMN_Big(2,1,1,2);
	pq.push(e1);

	__int64 aaa,pqmax=0;
	while(pq.empty()==false){
		e1=pq.top();
	pq.pop();
		
		if(e1.b>LIMIT)break;
		
		aaa=e1.b;
		ansA+=(e1.a<=LIMIT)*e1.addA;
		ansB+=e1.addB;
		addACount++;
		addBCount+=(e1.addB>0);
		e2.setMN_Big(e1.m,e1.n,e1.q+1,e1.addN);			
		pq.push(e2);
		if(e1.q==1){
			if(e1.n<=2||e1.m-2<=e1.n){
				if(down.find(e1.m+1)==down.end()){
					e2.setMN_Big(e1.m+1,1+(e1.m+1)%2,1,2);
					pq.push(e2);
					down[e1.m+1]=1+(e1.m+1)%2;
					if(1+(e1.m+1)%2<e1.m){
						e2.setMN_Big(e1.m+1,e1.m,1,-2);
						pq.push(e2);
						up[e1.m+1]=e1.m-1;
					}
				}
			}
		}
		int nextN=e1.nextN();
		if(nextN!=-1){
			e2.setMN_Big(e1.m,nextN,1,e1.addN);
			pq.push(e2);
			if(e1.addN==2){
				down[e1.m]=nextN;
			}else if(e1.addN==-2){
				up[e1.m]=nextN;
			}
		}
		if(pqmax<pq.size())pqmax=pq.size();
		
 	}
	all=ansA+ansB;
	std::cout<<"ans="<<all<<"\nMaxPriorityQueueSize"<<pqmax<<"\n";
}