UVa 12843 - Disputed Claims

Source

Second UVa regional warmup(20141101)
UVa 12843

問題概要

$3$ 辺の長さが全て整数の直角三角形で面積が $A$ になるものを列挙し,それらの $3$ 辺の長さを求める問題.

解法

$2A$ の約数を($\sqrt{2A}$ まで)列挙し,それを底辺に割り振る.
高さは $2A$ を底辺で割ったものになり,底辺と高さの自乗和が平方数になっていれば,そのルートが斜辺の長さ.
時間計算量は $O(T \sqrt{A})$ 程度.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年11月19日12時15分23秒
Last modified: 2014年11月08日19時28分52秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20141101_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: