結果

問題 No.2806 Cornflake Man
ユーザー ra5anchorra5anchor
提出日時 2024-07-13 20:13:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,442 bytes
コンパイル時間 377 ms
コンパイル使用メモリ 82,312 KB
実行使用メモリ 139,204 KB
最終ジャッジ日時 2024-07-13 20:13:14
合計ジャッジ時間 4,907 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 227 ms
110,040 KB
testcase_01 WA -
testcase_02 AC 143 ms
105,892 KB
testcase_03 WA -
testcase_04 AC 145 ms
80,896 KB
testcase_05 WA -
testcase_06 AC 160 ms
96,096 KB
testcase_07 WA -
testcase_08 AC 191 ms
93,652 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 41 ms
53,140 KB
testcase_17 AC 40 ms
53,140 KB
testcase_18 AC 41 ms
52,596 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def is_prime(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False
        prime += step
        step = 6 - step
    return True
def suspect(a, t, n):
    x = pow(a, t, n)
    n1 = n - 1
    while t != n1 and x != 1 and x != n1:
        x = pow(x, 2, n)
        t <<= 1
    return t & 1 or x == n1
def miller_rabin(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    check_list = (2, 7, 61) if n < 2 ** 32 else (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
    for i in check_list:
        if i >= n:
            break
        if not suspect(i, d, n):
            return False
    return True


N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
stA = set(A)

stA.discard(0)

if A[1] == 1:
    if M+1 == N:
        print(1)
        exit()
    else:
        print(-1)
        exit()

primes = []
for item in A:
    if miller_rabin(item):
        primes.append(item)

primes.sort()
ansset = set()

for p in primes:
    for i in range(p, M+1, p):
        ansset.add(i)
if ansset == stA:
    print(len(primes))
    print(*primes)
else:
    print(-1)
0