結果

問題 No.3301 Make Right Triangle
コンテスト
ユーザー toufu24
提出日時 2025-10-05 15:49:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,731 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 92,836 KB
最終ジャッジ日時 2025-10-05 15:49:40
合計ジャッジ時間 5,077 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other WA * 1 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
import sys
from math import gcd, isqrt

# 元の C++ に合わせた関数群


def prime_factorize(N: int):
    """(p, e) のリストを返す．"""
    res = []
    n = N
    p = 2
    while p * p <= n:
        if n % p != 0:
            p += 1 if p == 2 else 2  # 2 の次は奇数だけ試す小さな最適化
            continue
        e = 0
        while n % p == 0:
            e += 1
            n //= p
        res.append((p, e))
        p += 1 if p == 2 else 2
    if n != 1:
        res.append((n, 1))
    return res


def calc_divisors(N: int):
    """N の全ての約数をソートされたリストで返す．"""
    res = []
    i = 1
    # isqrt を使って整数の平方根まで走査
    r = isqrt(N)
    for i in range(1, r + 1):
        if N % i != 0:
            continue
        res.append(i)
        if N // i != i:
            res.append(N // i)
    res.sort()
    return res


def pow2(n: int):
    return n * n


def main():
    t = int(input())
    out_lines = []
    for _ in range(t):
        L = int(input())
        if L % 2 == 0:
            tmp = L // 2
            factors = prime_factorize(tmp)
            # 元の C++ と同様に，最初の素因子 (prime, exponent) を掛け合わせて m を作る
            if not factors:
                raise ValueError(
                    "tmp == 1 のとき，元の実装は factors[0] を参照します．入力制約を確認してください．"
                )
            m = factors[0][0] * factors[0][1]
            n = tmp // m
            if m * m - n * n < 0:
                m, n = n, m
            a = m * m - n * n
            b = 2 * m * n
            c = m * m + n * n
            # アサートはデバッグ用．必要なら外してください．
            assert pow2(a) + pow2(b) == pow2(c)
            out_lines.append(f"{a} {b} {c}")
        else:
            divs = calc_divisors(L)
            printed = False
            for p in divs:
                q = L // p
                gc = gcd(p, q)
                p0 = p // gc
                q0 = q // gc
                p, q = p0, q0
                if p * p - q * q < 0:
                    p, q = q, p
                if (pow2(p) + pow2(q)) % 2 == 0 and (pow2(p) - pow2(q)) % 2 == 0:
                    a = (p * p - q * q) // 2 * gc
                    b = p * q * gc
                    c = (p * p + q * q) // 2 * gc
                    assert pow2(a) + pow2(b) == pow2(c)
                    out_lines.append(f"{a} {b} {c}")
                    printed = True
                    break
            if not printed:
                assert False
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()
0