結果

問題 No.3663 LCM Decomposition
コンテスト
ユーザー LyricalMaestro
提出日時 2026-11-20 01:26:20
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 2,276 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 91 ms
コンパイル使用メモリ 64,464 KB
実行使用メモリ 115,692 KB
最終ジャッジ日時 2026-11-20 01:26:40
合計ジャッジ時間 19,795 ms
ジャッジサーバーID
(参考情報)
judge1_0 / judge4_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 7 TLE * 5 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

# https://yukicoder.me/problems/no/3663

import math

def prime_decomp(N):
    sqrt_n = int(math.sqrt(N))
    p_map = {}
    for p in range(2, sqrt_n + 1):
        if N % p == 0:
            cnt = 0
            while N % p == 0:
                cnt += 1
                N //= p
            p_map[p] = cnt
    if N > 1:
        p_map[N] = 1
    return p_map

def get_divisors(N):
    sqrt_n = int(math.sqrt(N))
    divisors = []
    for p in range(1, sqrt_n + 1):
        if N % p == 0:
            q = N // p
            divisors.append(p)
            if q != p:
                divisors.append(q)
    return divisors
            


def solve(N, L, R):

    p_map = prime_decomp(N)
    divisors = get_divisors(N)

    p_array = [(p, e) for p, e in p_map.items()]
    p_array.sort(key=lambda x: x[0])
    p_array2 = [p ** e for p, e in p_array]

    target_divisors = []
    for d in divisors:
        if L <= d <= R:
            bit = 0
            for i in range(len(p_array2)):
                if d % p_array2[i] == 0:
                    bit |= 1 << i
            target_divisors.append((d, bit))

    prevs = [{} for _ in range(len(target_divisors) + 1)]
    prevs[0][(0, 0)] = -1

    for index in range(len(target_divisors)):
        d, bit = target_divisors[index]

        for key in prevs[index].keys():
            count, current_bit = key

            prevs[index + 1][key] = (key, d)
            if count <= 2:
                new_count = count + 1
                new_bit = current_bit | bit
                prevs[index + 1][(new_count, new_bit)] = (key, d)

    target_key = (3, 2 ** len(p_array2) - 1)
    if target_key in prevs[-1]:
        key = target_key
        answer = []
        for i in reversed(range(1, len(target_divisors) + 1)):
            p = prevs[i][key]
            next_key, d = p
            if next_key[0] < key[0]:
                answer.append(d)
            key= next_key
        answer.sort()
        return " ".join(map(str, answer))
    else:
        return -1











def main():
    T = int(input())
    answers = []
    for _ in range(T):
        N, L, R = map(int, input().split())
        ans = solve(N, L, R)
        answers.append(ans)

    for ans in answers:
        print(ans)

    

if __name__ == "__main__":
    main()
0