天下一プログラマーコンテスト2015 本戦（オープン） : D - ほぼピタゴラスの三角形

これオンサイトも本番誰も解けてなかったみたいね。
http://tenka1-2015-final-open.contest.atcoder.jp/tasks/tenka1_2015_final_d

問題

3辺の長さがa,b,cの三角形のうち、入力L,sに対して以下を満たすものは何通りあるか。

• a,b,cはa≦b≦cかつgcd(a,b,c)=1を満たす自然数。
• a^2+b^2+s^2=c^2
• a+b+c≦L

解法

自分ではどうにもならないので公式解説を見て回答。

s=0の時、(a,b,c)は直角三角形の３辺を表すものとなる。
列ベクトル(a,b,c)に対し、以下の３つの行列を順次掛けていくとすべてのピタゴラス数を列挙できる。

[+1 -2 +2] [+1 +2 +2] [-1 +2 +2] 
[+2 -1 -2] [+2 +1 +2] [-2 +1 +2]
[+2 -2 +3] [+2 +2 +3] [-2 +2 +3]

上記行列は、c^2-a^2-b^2の値を保つ。
よって、ピタゴラス数でなくてもa^2+b^2+s^2=c^2であるような(a,b,c)に対し上記行列を適用していっても、a^2+b^2+s^2=c^2を満たす(a,b,c)を列挙できる。
上記式と三角形の条件より、a＜2s、また(c-b)(c+b)=a^2+s^2。
そこでaをこの範囲で総当たりし、またb,cを求めよう。
後は上記３種類の行列をDFSの要領でどんどん掛けて、条件を満たす(a,b,c)を列挙する。

ll L,S;
ll ret;
set<int> SS[50501];

void dfs(int a,int b,int c,int step) {
	if(a+b+c>L) return;
	
	int x=__gcd(a,b);
	if(x>1 && __gcd(x,c)>1) return;
	
	if(a<=10100) {
		if(SS[a].count(b)) return;
		SS[a].insert(b);
	}
	if(a && a+b>c) ret++;
	
	dfs(1*a-2*b+2*c,2*a-1*b+2*c,2*a-2*b+3*c,step+1);
	if(a<b) dfs(-2*a+1*b+2*c,-1*a+2*b+2*c,-2*a+2*b+3*c,step+1);
	dfs(2*a+1*b+2*c,1*a+2*b+2*c,2*a+2*b+3*c,step+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	int a,b,c,g;
	cin>>L>>S;
	
	for(a=0;a<=2*S;a++) {
		ll d = a*a+S*S;
		for(ll cb=1;cb*cb<d;cb++) if(d % cb==0) {
			ll cb2=d/cb;
			if((cb+cb2)%2) continue;
			c = (cb+cb2)/2;
			b = (cb2-cb)/2;
			dfs(min(a,b),max(a,b),c,0);
		}
	}
	
	cout<<ret<<endl;
}

まとめ

ピタゴラスの三分木って他にネットで情報出てこないけど有名な式なの…？