結果
問題 | No.2081 Make a Test Case of GCD Subset |
ユーザー | 👑 rin204 |
提出日時 | 2022-09-26 19:58:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 143 ms / 2,000 ms |
コード長 | 2,448 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 87,052 KB |
実行使用メモリ | 76,932 KB |
最終ジャッジ日時 | 2023-08-24 03:01:48 |
合計ジャッジ時間 | 7,694 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
71,808 KB |
testcase_01 | AC | 90 ms
76,772 KB |
testcase_02 | AC | 97 ms
76,612 KB |
testcase_03 | AC | 87 ms
76,824 KB |
testcase_04 | AC | 89 ms
76,748 KB |
testcase_05 | AC | 91 ms
76,720 KB |
testcase_06 | AC | 93 ms
76,528 KB |
testcase_07 | AC | 84 ms
76,720 KB |
testcase_08 | AC | 107 ms
76,676 KB |
testcase_09 | AC | 89 ms
76,544 KB |
testcase_10 | AC | 93 ms
76,788 KB |
testcase_11 | AC | 94 ms
76,768 KB |
testcase_12 | AC | 94 ms
76,376 KB |
testcase_13 | AC | 95 ms
76,760 KB |
testcase_14 | AC | 143 ms
76,932 KB |
testcase_15 | AC | 87 ms
76,532 KB |
testcase_16 | AC | 98 ms
76,508 KB |
testcase_17 | AC | 96 ms
76,852 KB |
testcase_18 | AC | 87 ms
76,536 KB |
testcase_19 | AC | 102 ms
76,648 KB |
testcase_20 | AC | 88 ms
76,816 KB |
testcase_21 | AC | 88 ms
76,584 KB |
testcase_22 | AC | 87 ms
76,444 KB |
testcase_23 | AC | 76 ms
76,092 KB |
testcase_24 | AC | 70 ms
71,924 KB |
testcase_25 | AC | 72 ms
72,056 KB |
testcase_26 | AC | 71 ms
72,048 KB |
testcase_27 | AC | 77 ms
76,276 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))