結果
問題 | No.2081 Make a Test Case of GCD Subset |
ユーザー | 👑 rin204 |
提出日時 | 2022-09-26 19:58:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 2,448 bytes |
コンパイル時間 | 200 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 65,152 KB |
最終ジャッジ日時 | 2024-06-02 00:16:16 |
合計ジャッジ時間 | 4,894 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
52,992 KB |
testcase_01 | AC | 54 ms
63,232 KB |
testcase_02 | AC | 59 ms
63,872 KB |
testcase_03 | AC | 54 ms
63,232 KB |
testcase_04 | AC | 52 ms
63,488 KB |
testcase_05 | AC | 52 ms
62,848 KB |
testcase_06 | AC | 57 ms
63,104 KB |
testcase_07 | AC | 50 ms
62,208 KB |
testcase_08 | AC | 66 ms
63,360 KB |
testcase_09 | AC | 52 ms
63,360 KB |
testcase_10 | AC | 57 ms
63,360 KB |
testcase_11 | AC | 56 ms
63,488 KB |
testcase_12 | AC | 55 ms
63,564 KB |
testcase_13 | AC | 57 ms
62,976 KB |
testcase_14 | AC | 96 ms
65,152 KB |
testcase_15 | AC | 49 ms
62,848 KB |
testcase_16 | AC | 57 ms
62,976 KB |
testcase_17 | AC | 55 ms
63,104 KB |
testcase_18 | AC | 46 ms
61,568 KB |
testcase_19 | AC | 61 ms
63,488 KB |
testcase_20 | AC | 50 ms
62,464 KB |
testcase_21 | AC | 47 ms
62,208 KB |
testcase_22 | AC | 46 ms
62,592 KB |
testcase_23 | AC | 39 ms
58,752 KB |
testcase_24 | AC | 36 ms
52,992 KB |
testcase_25 | AC | 36 ms
52,608 KB |
testcase_26 | AC | 36 ms
52,864 KB |
testcase_27 | AC | 40 ms
58,752 KB |
ソースコード
from math import gcd def enumerate_primes(n): if n <= 1: return [] A = [1, 7, 11, 13, 17, 19, 23, 29] thres = (n + 29) // 30 sieve = [255] * (thres + int(n ** 0.5) + 10) ntoi = lambda i: (i >> 2) + (not (~i&19)) sieve[0] ^= 1 i = 0 flg = 1 while flg: if sieve[i] != 0: for j in range(8): if sieve[i] >> j & 1: p = i * 30 + A[j] if (p * p > n): flg = 0 continue q = [0] * 8 r = [0] * 8 s = 0 for k in range(8): x = p * (i * 30 + A[k]) q[k] = x // 30 r[k] = ntoi(x - 30 * q[k]) while q[0] + s < thres: sieve[q[0] + s] &= ~(1 << r[0]) sieve[q[1] + s] &= ~(1 << r[1]) sieve[q[2] + s] &= ~(1 << r[2]) sieve[q[3] + s] &= ~(1 << r[3]) sieve[q[4] + s] &= ~(1 << r[4]) sieve[q[5] + s] &= ~(1 << r[5]) sieve[q[6] + s] &= ~(1 << r[6]) sieve[q[7] + s] &= ~(1 << r[7]) s += p i += 1 primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] for i in range(1, thres): for j in range(8): if sieve[i] >> j & 1: primes.append(i * 30 + A[j]) while primes[-1] > n: primes.pop() return primes m = int(input()) if m == 0: m += 998244353 A = [] primes = enumerate_primes(300)[:30] ind = 0 x = (1 << 30) - 1 se = set() while x > 0: if x > m: x >>= 1 continue m -= x p = primes[ind] y = p c = x.bit_length() B = [] while c > 0: ok = True for q in primes: if p != q and y % q == 0: ok = False break if ok: for a in A: if gcd(a, y) != 1: ok = False break if y in se: ok = False if ok: yy = y while c > 0 and yy <= 10 ** 5: se.add(yy) c -= 1 B.append(yy) yy *= p y += p A += B ind += 1 print(len(A)) print(*A) print(max(A))