結果

問題 No.3663 LCM Decomposition
コンテスト
ユーザー kidodesu
提出日時 2026-09-30 20:53:42
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 371 ms / 1,000 ms
+ 322µs
コード長 1,887 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 63 ms
コンパイル使用メモリ 81,672 KB
実行使用メモリ 84,876 KB
最終ジャッジ日時 2026-09-30 20:53:47
合計ジャッジ時間 4,548 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    n, l, r = list(map(int, input().split()))
    D = {}
    a = 2
    m = n
    while a*a <= m:
        c = 0
        while not m % a:
            c += 1
            m //= a
        if c:
            D[a] = c
        a += 1
    if m-1:
        D[m] = 1
    C = set()
    a = 1
    while a*a <= n:
        if not n % a:
            C.add(a)
            C.add(n//a)
        a += 1
    C = list(C)
    E = list(D.keys())
    N = len(D)
    dp = [[] for _ in range(1<<N)]
    X = []
    for a in C:
        if l <= a <= r:
            b = a
            X.append(a)
            t = 0
            for i in range(N):
                d = E[i]
                c = 0
                while not a % d:
                    c += 1
                    a //= d
                if c == D[d]:
                    t |= 1 << i
            dp[t].append(b)
    for i in range(N):
        for bit in range(1<<N):
            if not bit >> i & 1:
                for j in range(max(0, min(3-len(dp[bit]), len(dp[bit|1<<i])))):
                    dp[bit].append(dp[bit|1<<i][j])
    #print(dp)
    for bit0 in range(1<<N):
        if not dp[bit0]: continue
        x0 = dp[bit0][0]
        for bit1 in range(1<<N):
            i = 0
            x1 = -1
            while i < len(dp[bit1]):
                if x0 != dp[bit1][i]:
                    x1 = dp[bit1][i]
                    break
                else:
                    i += 1
            if x1 == -1: continue
            bit2 = (1<<N)-1 ^ (bit0 | bit1)
            i = 0
            x2 = -1
            while i < len(dp[bit2]):
                if x0 != dp[bit2][i] and x1 != dp[bit2][i]:
                    x2 = dp[bit2][i]
                    break
                else:
                    i += 1
            if x2 != -1:
                return sorted([x0, x1, x2])
    return [-1]
for _ in range(int(input())):
    print(*main())
0