#1179599 (PyPy3) No.3663 LCM Decomposition

• 問題: No.3663 LCM Decomposition
• ユーザー: sepa38
• 提出日時: 2026-08-28 15:45:37
• 言語: PyPy3 (7.3.23)
• 結果: AC
• 実行時間: 253 ms / 1,000 ms
• コード長: 3,486 bytes
• コンパイル時間: 240 ms
• コンパイル使用メモリ: 96,360 KB
• 実行使用メモリ: 88,004 KB
• 最終ジャッジ日時: 2026-08-30 13:05:24
• 合計ジャッジ時間: 4,561 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 14

ソースコード

# 素数判定 (Miller-Rabin, n < 2^64 で決定的) と素因数分解 (Pollard's rho)
# 試し割りより高速。10^18 程度の素因数分解も現実的
from math import gcd
import random


def is_prime(n):
    if n < 2:
        return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % p == 0:
            return n == p
    d = n - 1
    s = (d & -d).bit_length() - 1
    d >>= s
    for a in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True


def _pollard(n):
    if n % 2 == 0:
        return 2
    while True:
        c = random.randrange(1, n)
        x = y = 2
        d = 1
        while d == 1:
            x = (x * x + c) % n
            y = (y * y + c) % n
            y = (y * y + c) % n
            d = gcd(abs(x - y), n)
        if d != n:
            return d


def factorize(n):  # {素因数: 指数} を返す (sieve.factorize は [(p,e)] なので注意)
    res = {}
    stack = [n] if n > 1 else []
    while stack:
        m = stack.pop()
        if is_prime(m):
            res[m] = res.get(m, 0) + 1
        else:
            d = _pollard(m)
            stack.append(d)
            stack.append(m // d)
    return res


for _ in range(int(input())):
    n, l, r = map(int, input().split())

    if n == 1:
        print(-1)
        continue

    fac = factorize(n)

    d = [1]
    ls = []

    for pi in fac:
        ls.append(pow(pi, fac[pi]))
        x = 1
        ln = len(d)
        for _ in range(fac[pi]):
            x *= pi
            for i in range(ln):
                d.append(d[i]*x)

    k = len(ls)

    exact_mask = [[] for _ in range(1 << k)]
    for v in d:
        if l <= v <= r:
            mask = 0
            for i in range(k):
                if v % ls[i] == 0:
                    mask |= (1 << i)

            if len(exact_mask[mask]) < 3:
                exact_mask[mask].append(v)

    cover = [[] for _ in range(1 << k)]
    for mask in range(1 << k):
        if not exact_mask[mask]:
            continue
        sub = mask
        while True:
            for val in exact_mask[mask]:
                if val not in cover[sub]:
                    cover[sub].append(val)
                    if len(cover[sub]) > 3:
                        cover[sub].pop()

            if not sub:
                break
            sub = (sub - 1) & mask

    ans = []
    m = (1 << k) - 1

    for a in range(1 << k):
        ca = cover[a]
        if not ca:
            continue
        rem = m ^ a
        b = rem
        while True:
            c = rem ^ b
            cb = cover[b]
            cc = cover[c]

            if cb and cc:
                for va in ca:
                    for vb in cb:
                        if va == vb: continue
                        for vc in cc:
                            if va == vc or vb == vc: continue
                            ans = sorted([va, vb, vc])
                            break
                        if ans:
                            break
                    if ans:
                        break

            if ans:
                break
            if not b:
                break
            b = (b - 1) & rem

        if ans:
            break

    if ans:
        print(*ans)
    else:
        print(-1)