結果

問題 No.3663 LCM Decomposition
コンテスト
ユーザー t5ugu
提出日時 2026-08-27 15:23:44
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 1,579 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 234 ms
コンパイル使用メモリ 95,984 KB
実行使用メモリ 143,232 KB
最終ジャッジ日時 2026-08-30 13:04:23
合計ジャッジ時間 4,718 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import sqrt, lcm

def factorization(n: int) -> list[int]:
    '''
    素因数分解。
    see: https://qiita.com/gafugafu/items/482e29b879f2a827a53d
    '''
    factors: list[int] = []
    if n < 1:
        return [-1]
    elif n == 1:
        return [1]

    n1 = n
    for i in range(2, int(sqrt(n))+1):
        if n1 % i == 0:
            while n1 % i == 0:
                n1//=i
                factors.append(i)
                if n1 == 1:
                    return factors
    if n1 != 1:
        factors.append(n1)
        return factors
    elif factors == []:
        return [n]
    return []

def divisors(n: int) -> list[int]:
    '''
    約数全列挙
    '''
    factors = factorization(n)

    ds = [1]

    for p in factors:
        l = len(ds)
        for i in range(l):
            ds.append(p * ds[i])

    # 昇順かつ重複なしで返す
    ds.sort()
    return sorted(set(ds), key=ds.index)

def solve(N: int, L: int, R: int):
    D = divisors(N) # len(D) = O(N^{1/3}) ~ 10^3
    DD = [d for d in D if L <= d <= R]
    lDD = len(DD)
    for i in range(lDD):
        for j in range(i+1, lDD):
            for k in range(j+1, lDD):
                if lcm(DD[i], DD[j], DD[k]) == N:
                    return [DD[i], DD[j], DD[k]]
    return [-1]

T = int(input())
# 3重ループを軽減するのがセオリーだが......
cache : dict[tuple[int, int, int], list[int]] = {}

for _ in range(T):
    N, L, R = map(int, input().split())
    if (N, L, R) not in cache:
        cache[(N, L, R)] = solve(N, L, R)
    print(*cache[(N, L, R)])
0