結果

問題 No.3663 LCM Decomposition
コンテスト
ユーザー 👑 loop0919
提出日時 2026-08-30 16:26:54
言語 PyPy3
(7.3.23)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 751 ms / 1,000 ms
+ 577µs
コード長 1,692 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 269 ms
コンパイル使用メモリ 95,848 KB
実行使用メモリ 89,420 KB
最終ジャッジ日時 2026-08-30 16:27:08
合計ジャッジ時間 7,754 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import defaultdict
from copy import deepcopy
from math import isqrt


def divisors(n):
    lower, upper = [], []
    for i in range(1, isqrt(n) + 1):
        if n % i == 0:
            lower.append(i)
            upper.append(n // i)

    if lower[-1] == upper[-1]:
        upper.pop()

    return lower + upper[::-1]


def factorize(n):
    _n = n
    i = 2
    facts = defaultdict(int)

    while i**2 <= _n:
        while _n % i == 0:
            facts[i] += 1
            _n //= i
        i += 1

    if _n > 1:
        facts[_n] += 1

    return facts


def solve():
    N, L, R = [int(s) for s in input().split()]
    divs = [d for d in divisors(N) if L <= d <= R]
    facts = factorize(N)

    size = len(facts)
    keys = sorted(facts.keys())

    dp = [[None] * (1 << size) for _ in range(4)]
    dp[0][0] = []

    for d in divs:
        ndp = [dp[i][:] for i in range(4)]

        B = 0
        for idx, k in enumerate(keys):
            _d = d
            for _ in range(facts[k]):
                if _d % k == 0:
                    _d //= k
                else:
                    break
            else:
                B |= 1 << idx
        for times in range(3):
            for bit in range(1 << size):
                if dp[times][bit] is None:
                    continue

                nbit = bit | B
                if ndp[times + 1][nbit] is None:
                    ndp[times + 1][nbit] = dp[times][bit] + [d]

        if ndp[3][(1 << size) - 1] is not None:
            print(*ndp[3][(1 << size) - 1])
            return

        dp = ndp

    print(-1)


if __name__ == "__main__":
    T = int(input())

    for _ in range(T):
        solve()
0