問題概要
問題URL
問題文
長さが $L$ である辺を含み、すべての辺の長さが正整数である直角三角形を構築してください。
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- $1 \leq T \leq 10^5$
- $1 \leq L \leq 10^9$
- 入力はすべて整数である
解説
ピタゴラス数の性質を利用します。
正整数 $m, n$ について、
$$(A, B, C) = (m^2 - n^2, 2mn, m^2 + n^2)$$
なる $A, B, C$ は必ず直角三角形をなします。このような $m, n$ を見つければ良いです。
L が偶数のとき
$m = \frac{L}{2}, ~ n = 1$ とすることで、$B = L$ となります。
L が奇数のとき
$x^2 - (x - 1)^2 = 2x - 1$ を利用します。
$L = 2 x - 1 \Leftrightarrow x = \frac{L - 1}{2}$ となる $x$ について、 $m = x, ~ n = x - 1$ とすることで $A = L$ とすることができます。
このようにして各質問に対して計算量 $O(1)$ で求めることができました。
$A, B, C$ の大きさは $O(L^2)$ となり、$64$-bit 整数型の範囲で十分収まります。
余談
MMA Contest 020 オンサイトで参加していました！めちゃくちゃ面白かったです。
ユーザー解説を書くことでゆるふわポイントなるものが得られるみたいなので、稼いでみました。