結果
| 問題 |
No.3301 Make Right Triangle
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2025-10-05 16:16:34 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,551 bytes |
| コンパイル時間 | 344 ms |
| コンパイル使用メモリ | 82,240 KB |
| 実行使用メモリ | 312,588 KB |
| 最終ジャッジ日時 | 2025-10-05 16:16:42 |
| 合計ジャッジ時間 | 7,532 ms |
|
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 8 |
ソースコード
from math import gcd, isqrt
def gen_divisors(n):
assert n >= 2
ret = []
for i in range(2, isqrt(n) + 1):
if n % i == 0:
ret.append(i)
if i * i != n:
ret.append(i)
return ret
def is_prime(n):
assert n >= 2
for i in range(2, isqrt(n) + 1):
if n % i == 0:
return False
return True
t = int(input())
for _ in range(t):
l = int(input())
# Lを斜辺にするか、底辺にするか...
# 斜辺にしてみる
# L^2 = A^2 + B^2を満たす、A, Bの整数解
# Lはクソデカ
# A^2の方を全探索するよなあ
# L^2 - A^2 = B^2
# A^2を全探索して、B^2が平方数だったら勝ち
# でもテストケース多いしクソデカですよ????
# Lを斜辺とすると、他の辺はLより短い
# L^2 > A^2, B^2
# うーん?
# 底辺にしてみる
# A^2 = L^2 + B^2
# A^2 - B^2 = L^2 (!!!)
# (A - B)(A + B) = L^2
# L^2の素因数をいい感じに管理するのか?
# や、同じだなあ
# ユークリッドの式なるものがある
# うまくいかんなあ
# 列挙して、割れるやつを倍にしたらよい?
# lが素数だとかなり時間がかかる
# lがm^2 - n^2 = (m - n)(m + n), 2mn, n^2 + m^2のどれかで割り切れてほしい
d = {i**2: i for i in range(1, isqrt(10**9) + 1)}
if is_prime(l):
for k, v in d.items():
if l - k in d:
m = d[max(k, l - k)]
n = d[min(k, l - k)]
a, b, c = m**2 - n**2, 2 * m * n, m**2 + n**2
print(a, b, c, m, n)
break
else:
for m in range(1, isqrt(l) + 1):
f = False
for n in range(1, m):
if gcd(n, m) != 1:
continue
if n % 2 == m % 2:
continue
a, b, c = m**2 - n**2, 2 * m * n, m**2 + n**2
if l % a == 0:
x = l // a
print(a * x, b * x, c * x)
f = True
break
elif l % b == 0:
x = l // b
print(a * x, b * x, c * x)
f = True
break
elif l % c == 0:
x = l // c
print(a * x, b * x, c * x)
f = True
break
if f:
break