Codeforces #512 Div1 A. Vasya and Triangle

本番無駄に頑張りすぎた。
http://codeforces.com/contest/1053/problem/A

問題

正整数N,M,Kが与えられる。
0≦x≦N、0≦y≦Mの範囲で格子点を３つ選んで三角形を作るとき、面積N*M/Kの物を構築できるか。

解法

(0,0),(A,0),(0,B)を結んだ三角形を作ることを考える。
ABK=2NMであるA,Bを選べばよい。

まずNM/Kを約分しできるか判定し、分母が1,2以外になるなら不可である。

あとはA=N/gcd(K,N)、B=M/(K/(gcd(K,N))とする。
NM/Kを約分した場合分母が1になるなら、A,Bのうち倍にしてもN,Mを超えない方を倍にしよう。

ll X,Y,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y>>K;
	
	if(2*X*Y%K) return _P("NO\n");
	ll A=X,B=Y;
	ll g=__gcd(A,K);
	A/=g;
	K/=g;
	g=__gcd(B,K);
	B/=g;
	K/=g;
	
	if(K==1) {
		if(2*A<=X) A*=2;
		else B*=2;
	}
	
	
	cout<<"YES"<<endl;
	cout<<0<<" "<<0<<endl;
	cout<<A<<" "<<0<<endl;
	cout<<0<<" "<<B<<endl;
}

まとめ

本番自身が持てなくて無駄な処理を繰り返してしまった。