結果

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

ソースコード

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, L, R = map(int, input().split())
    assert 1 <= N <= 1_000_000_000
    assert 1 <= L <= R <= 1_000_000_000
    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())
assert 1 <= T <= 1000
for _ in range(T):
    print(*solve())
0