#1179510 (PyPy3) No.3663 LCM Decomposition

• 問題: No.3663 LCM Decomposition
• ユーザー: sepa38
• 提出日時: 2026-08-27 21:44:27
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 3,272 bytes
• コンパイル時間: 263 ms
• コンパイル使用メモリ: 96,108 KB
• 実行使用メモリ: 87,368 KB
• 最終ジャッジ日時: 2026-08-30 13:04:34
• 合計ジャッジ時間: 9,151 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 11 TLE * 3

ソースコード

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


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


def dfs(x, org_fac, pis, idx, n_fac, l, r):
    if idx == len(pis):
        return -1
    if (l - 1) // x == r // x:
        return -1

    if l <= x <= r:
        return x

    if pis[idx] in org_fac:
        return dfs(x, org_fac, pis, idx+1, n_fac, l, r)

    y = 1
    for j in range(n_fac[pis[idx]]+1):
        res = dfs(x*y, org_fac, pis, idx+1, n_fac, l, r)
        if res > 0:
            return res

        y *= pis[idx]

    return -1


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)

    d.sort()

    bc = [v for v in d if l <= v <= r]
    bc.sort()

    ans = [-1] * 3

    for ic in reversed(range(len(bc))):
        c = bc[ic]
        for ib in reversed(range(ic)):
            b = bc[ib]

            x = 1  # a は x の倍数
            for v in ls:
                if c % v and b % v:
                    x *= v

            if x >= b:
                continue

            # a = x*k とおく
            kmin = (l + x - 1) // x
            kmax = (b - 1) // x

            le = bisect.bisect_left(d, kmin)
            ri = bisect.bisect_right(d, kmax)

            rem = n // x

            for ki in range(le, ri):  # 結構狭そうではあるけどこれ間に合うのか？
                k = d[ki]
                if rem % k == 0:
                    a = x*k
                    ans = [a, b, c]
                    break

            if ans[0] > 0:
                break
        if ans[0] > 0:
            break

    if ans[0] > 0:
        print(*ans)
    else:
        print(-1)