結果

問題 No.3301 Make Right Triangle
ユーザー kmmtkm
提出日時 2025-10-05 16:30:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,866 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 77,932 KB
最終ジャッジ日時 2025-10-05 16:30:32
合計ジャッジ時間 7,082 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 自作ライブラリ
# https://github.com/takumi-okamoto/competitive-programming-public/tree/main/mylib

import sys
import math


# sys.setrecursionlimit(10**8)


def debug(*args):
    print(*args, file=sys.stderr)


def solve(l):
    if l in [3, 4, 5]:
        return "3 4 5"

    # a = k(m**2-n**2)
    # b = 2kmn
    # c = k(m**2 + n**2)
    # gcd(m, n) = 1

    m = 1
    while m * m < l:
        # lが素数の場合
        # m ** 2 + n ** 2 = l
        n2 = l - m * m
        n1 = int(n2**0.5)
        for d in [-1, 0, 1]:
            n = n1 + d
            if n * n == n2:
                break
        else:
            n = None

        if n is not None:
            g = math.gcd(m, n)
            k = g**2
            m = m // g
            n = n // g
            if m > n:
                return f"{k*(m**2 - n**2)} {2*k*m*n} {k*(m**2+n**2)}"

        m += 1

    n = 1
    while 2 * n * n <= l:
        if l % (2 * n) == 0:
            m = l // (2 * n)
            if m > n:
                g = math.gcd(m, n)
                m //= g
                n //= g
                k = g * g
                return f"{k*(m**2 - n**2)} {2*k*m*n} {k*(m**2+n**2)}"
        n += 1

    d = 1
    while d * d <= l:
        if l % d == 0:
            if (l // d - d) % 2 == 0:
                n = (l // d - d) // 2
                m = 2 * n + d
                if m > n:
                    g = math.gcd(m, n)
                    m //= g
                    n //= g
                    k = g * g
                    return f"{k*(m**2 - n**2)} {2*k*m*n} {k*(m**2+n**2)}"
        d += 1


def main():
    t = int(input())
    ans = []
    for _ in range(t):
        ans.append(solve(int(input())))
    print(*ans, sep="\n")
    # for abc in ans:
    #     a, b, c = map(int, abc.split())
    #     assert a**2 + b**2 == c**2


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