yukicoder : No.1626 三角形の構築

登場する数値が地味に大きくてしんどい。
https://yukicoder.me/problems/no/1626

問題

三角形の面積Sと総長Tが与えられる。
この条件を満たす三角形のうち、辺の長さが整数となるものについて、その長さ{a,b,c}を列挙せよ。

解法

色々方法がありそう。
自分はヘロンの公式と、a+b+c=Tの2式に対し、cを総当たりすると変数が2個になるので、連立方程式を解いた。

int t;
ll S,T;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>t;
	while(t--) {
		cin>>S>>T;
		__int128 SS=(__int128)16*S*S;
		
		__int128 tt=T;
		__int128 t2=tt-tt/3+1;
		
		if(SS%tt) {
			cout<<0<<endl;
			continue;
		}
		SS/=tt;
		if(SS>t2*t2*t2) {
			cout<<0<<endl;
			continue;
		}
		
		ll S3=SS;
		ll a,b,c;
		vector<vector<ll>> ret;
		for(c=1;c*c*c<=S3;c++) if(S3%c==0 && (T-c)%2==0) {
			ll C=(T-c)/2;
			ll S=S3/c;
			
			ll X=-4;
			ll Y=4*T-4*C;
			ll Z=T*2*C-T*T-S;
			ll D=Y*Y-4*X*Z;
			if(D<0) continue;
			ll DR=round(sqrt(D));
			if(DR*DR!=D) continue;
			if((-Y+DR)%8) continue;
			if((-Y-DR)%8) continue;
			ll a=(-Y+DR)/(2*X);
			ll b=(-Y-DR)/(2*X);
			if(a<=0||b<=0) continue;
			if(a>b||b>C) continue;
			ret.push_back({a,b,C});
			
		}
		
		cout<<ret.size()<<endl;
		FORR(a,ret) cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
		
		
		
	}
}

まとめ

式変形が割と面倒だった。