yukicoder : No.1143 面積Nの三角形

コードは短いんだけどね。
https://yukicoder.me/problems/no/1143

問題

正整数Nが与えられる。
3辺の長さがいずれも整数の三角形のうち、面積がNとなるものは何通りか。

解法

ヘロンの公式を考えると、3辺の長さa,b,cに対しs=(a+b+c)/2とするとN^2=s(s-a)(s-b)(s-c)となるa,b,cを求める問題となる。
ここで、x=s-a、y=s-b、z=s-cとおくとx+y+z=3s-(a+b+c)=sとなるので、N^2=xyz(x+y+z)となる。

N^2は高々10^12なので、N^2の約数を列挙し、x,yを総当たりしよう。
それぞれzを求め、zが整数かつx≦y≦z≦Nとなるものを数え上げて行く。

ll N;

set<int> H[1010100];

ll issq(ll V) {
	ll a=sqrt(V);
	if(a*a==V) return a;
	if((a-1)*(a-1)==V) return a-1;
	if((a+1)*(a+1)==V) return a+1;
	return -1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll M=N*N;
	vector<ll> A;
	for(i=1;1LL*i*i<=M;i++) if(M%i==0) {
		A.push_back(i);
		if(1LL*i*i!=M) A.push_back(M/i);
	}
	
	sort(ALL(A));
	
	int num=0;
	FOR(x,A.size()) {
		if(A[x]>N) break;
		for(y=x;y<A.size();y++) {
			if(A[y]>N) break;
			if(M%(A[x]*A[y])) continue;
			ll c=-M/(A[x]*A[y]);
			ll b=A[x]+A[y];
			ll d=b*b-4*c;
			if(d<0) continue;
			ll v=issq(d);
			if(v<0) continue;
			v-=b;
			if(v<0) continue;
			if(v%2) continue;
			if(A[y]<=v/2 && v/2<N) num++;
			
			
			
		}
	}
	
	
	
	
	cout<<num<<endl;
	
}

まとめ

本番中、直角三角形を列挙して、それを2つ合わせるケースも考えたんだけど、2つくっ付けたらまた新たな直角三角形になるケースをどうしようかな…と思ってたら時間が終わった。