結果
問題 |
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