結果

問題 No.2953 Maximum Right Triangle
コンテスト
ユーザー daiota
提出日時 2024-11-08 23:17:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,105 bytes
コンパイル時間 1,835 ms
コンパイル使用メモリ 167,556 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 23:17:19
合計ジャッジ時間 2,181 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define REP(i,n) for(int i=0;i<int(n);i++)


ll extgcd(ll a,ll b,ll & x,ll & y){
	ll g;
	if(b!=0){
		g=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}else{
        g=a;
		x=1; y=0;
	}
	  return g;
}





int main(void){
	cin.tie(nullptr);  ios_base::sync_with_stdio(false);
	ll i,j;


	int T;
	cin >> T;
	while(T--){

		ll D,a,b;
		cin >> D >> a >> b;

		if(a==0){
			cout << b*D << endl;
			continue;
		}

		if(b==0){
			cout << a*D << endl;
			continue;
		}


		ll x,y;
		ll c=a*a+b*b;


		ll g=extgcd(a,b,x,y);

		if(c%g!=0){
			cout << 0 << endl;
			continue;
		}


		ll p=(-c*x/g+b/g-1)/(b/g),q=(D-c*x/g)/(b/g);
		ll qq=(c*y/g)/(a/g),pp=(c*y/g-D+a/g-1)/(a/g);

		if(max(p,pp)>min(q,qq)){
			cout << 0 << endl;
			continue;
		}

		ll u=max(p,pp),v=min(q,qq);

		ll X,Y,s,S;
		X=c*x/g+b*u/g;
		Y=c*y/g-a*u/g;

		s=2*max(a,X)*max(b,Y)-(a*b+X*Y+llabs(X-a)*llabs(Y-b));


		X=c*x/g+b*v/g;
		Y=c*y/g-a*v/g;

		S=2*max(a,X)*max(b,Y)-(a*b+X*Y+llabs(X-a)*llabs(Y-b));




		cout << max(s,S) << endl;





	}




	return 0;

}
0