Day 163-Q5 — 2026-09-28 — N 以下で約数が最も多い数（高度合成数。指数が広義単調減少の数だけを全列挙し、クエリは二分探索で答える）

📋 コピーimport sys
from bisect import bisect_right

LIMIT = 10**18
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]   # 2*3*...*47 <= 10^18 < 2*3*...*53


def candidates():
    """x = 2^e1 3^e2 5^e3 ...（e1 >= e2 >= ... >= 0）で x <= LIMIT のものを (x, 約数の個数) で全列挙"""
    res = []

    def dfs(i, x, d, max_e):
        res.append((x, d))
        if i == len(PRIMES):
            return
        p = PRIMES[i]
        for e in range(1, max_e + 1):
            if x > LIMIT // p:            # x * p > LIMIT
                break
            x *= p
            dfs(i + 1, x, d * (e + 1), e)  # 次の素数の指数は e 以下

    dfs(0, 1, 1, 64)
    res.sort()
    return res


def main():
    cand = candidates()
    xs = []
    best = []                      # best[j] = 小さい方から j 番目までの候補での (最大の約数の個数, その最小の x)
    bd, bx = 0, 0
    for x, d in cand:
        if d > bd:                 # 同数なら先に出た（小さい）x を残すので >（>= にしない）
            bd, bx = d, x
        xs.append(x)
        best.append((bd, bx))
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for i in range(t):
        j = bisect_right(xs, int(data[1 + i])) - 1   # x = 1 が必ず候補にあるので j >= 0
        d, x = best[j]
        out.append(f"{d} {x}")
    print("\n".join(out))


main()