読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #368 Div2 C. Pythagorean Triples

Codeforces

不参加でした。
http://codeforces.com/contest/707/problem/C

問題

正整数nが与えられる。
3辺の長さが整数で、うち1辺の長さがnの直角三角形が存在するなら、その長さを答えよ。

解法

nが2以下の場合は解無し。

  • nが奇数の場合、n,(n^2-1)/2,(n^2+1)/2で解となる。
  • nが偶数の場合でかつ2の累乗でない場合、nが奇数になるまで全体を2で割れば上記のパターンに持ち込める。
  • nが4以上の2の累乗の場合、(3,4,5)をn/4倍すればよい。
ll A,B,C;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A;
	if(A<=2) return _P("-1\n");
	if((A&(A-1))==0) {
		B=A*3/4;
		C=A*5/4;
	}
	else {
		x=0;
		while(A%2==0) x++, A/=2;
		B=(A*A-1)/2;
		C=B+1;
		while(x--) A*=2, B*=2, C*=2;
	}
	cout<<B<<" "<<C<<endl;
}

まとめ

解法色々ありそうだけど、一番シンプルなのどれかな。

広告を非表示にする