結果
問題 | No.2081 Make a Test Case of GCD Subset |
ユーザー | 👑 rin204 |
提出日時 | 2022-09-26 19:57:47 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,380 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 64,652 KB |
最終ジャッジ日時 | 2024-06-02 00:16:06 |
合計ジャッジ時間 | 3,874 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | AC | 34 ms
53,344 KB |
testcase_25 | AC | 34 ms
54,328 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
ソースコード
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 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 ok: yy = y while c > 0 and yy <= 10 ** 5: c -= 1 B.append(y) yy *= p y += p A += B ind += 1 print(len(A)) print(*A) print(max(A))