結果

問題 No.2081 Make a Test Case of GCD Subset
ユーザー LyricalMaestro
提出日時 2025-01-13 23:36:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,866 bytes
コンパイル時間 973 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 76,120 KB
最終ジャッジ日時 2025-01-13 23:36:50
合計ジャッジ時間 6,353 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


    

def main():
    M = int(input())
    if M == 0:
        M = 998244353

    # MAXまでの素数を求める
    MAX = 10 ** 5
    primes = []
    is_prime = [True] * (MAX + 1)
    for p in range(2, MAX + 1):
        if not is_prime[p]:
            continue
        primes.append(p)
        x = 2 * p
        while x <= MAX:
            is_prime[x] = False
            x += p

    # Mを2進数表現する
    array = []
    while M > 0:
        array.append(M % 2)
        M //= 2
    
    array.reverse()

    prime_buckets = [[] for _ in range(len(array))]
    p_index = 0
    for i in range(len(array)):
        if array[i] == 1:
            prime_buckets[i].append(primes[p_index])
            p_index += 1

    index = 0
    for p in primes[p_index:]:
        while index < len(array) and array[index] == 0:
            index += 1

        if index == len(array):
            break

        if len(prime_buckets[index]) < 20:
            prime_buckets[index].append(p)
        else:
            index += 1    

    def dfs(prime_arrays, index, A, a, n):
        if n == 0:
            return

        if index == len(prime_arrays) - 2:
            if a > 1 and a <= MAX:
                A.append(a)
            return
        
        while a <= MAX:
            dfs(prime_arrays, index + 1, A, a, n)
            if len(A) == n:
                return
            a *= prime_arrays[index]

    answer = []
    for i in range(len(array)):
        if array[i] == 1:
            n = len(array) - i - 1
            A = []
            dfs(prime_buckets[i], 0, A, 1, n)
            A = list(map(lambda x : x * prime_buckets[i][-2], A))
            A.append(prime_buckets[i][-1])
            answer += A
    
    print(len(answer))
    print(" ".join(map(str, answer)))











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