結果

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

ソースコード

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))]
    index = 0
    for p in primes:
        if array[index] == 1:   
            if len(prime_buckets[index]) < 6:
                prime_buckets[index].append(p)
        index += 1
        index %= len(array)
    

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

        if index == len(prime_arrays) - 1:
            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], 1, A, 1, n)
            A = list(map(lambda x : x * prime_buckets[i][0], A))
            A.append(prime_buckets[i][-1])
            answer += A
    
    len(answer)
    print(" ".join(map(str, answer)))











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