結果
問題 | No.2075 GCD Subsequence |
ユーザー | 👑 rin204 |
提出日時 | 2022-09-16 21:47:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,667 ms / 4,000 ms |
コード長 | 2,300 bytes |
コンパイル時間 | 307 ms |
コンパイル使用メモリ | 87,148 KB |
実行使用メモリ | 115,652 KB |
最終ジャッジ日時 | 2023-08-23 14:51:16 |
合計ジャッジ時間 | 53,931 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
79,372 KB |
testcase_01 | AC | 77 ms
79,248 KB |
testcase_02 | AC | 76 ms
79,436 KB |
testcase_03 | AC | 79 ms
79,388 KB |
testcase_04 | AC | 78 ms
79,328 KB |
testcase_05 | AC | 78 ms
79,140 KB |
testcase_06 | AC | 79 ms
79,472 KB |
testcase_07 | AC | 80 ms
78,916 KB |
testcase_08 | AC | 1,142 ms
103,776 KB |
testcase_09 | AC | 1,802 ms
114,808 KB |
testcase_10 | AC | 1,169 ms
102,928 KB |
testcase_11 | AC | 1,526 ms
109,072 KB |
testcase_12 | AC | 1,332 ms
105,992 KB |
testcase_13 | AC | 982 ms
98,916 KB |
testcase_14 | AC | 1,504 ms
109,160 KB |
testcase_15 | AC | 1,066 ms
101,264 KB |
testcase_16 | AC | 1,134 ms
103,312 KB |
testcase_17 | AC | 1,767 ms
114,692 KB |
testcase_18 | AC | 3,624 ms
115,496 KB |
testcase_19 | AC | 3,413 ms
115,644 KB |
testcase_20 | AC | 3,402 ms
115,364 KB |
testcase_21 | AC | 3,332 ms
115,440 KB |
testcase_22 | AC | 3,266 ms
115,224 KB |
testcase_23 | AC | 3,281 ms
115,572 KB |
testcase_24 | AC | 3,319 ms
115,652 KB |
testcase_25 | AC | 3,616 ms
115,252 KB |
testcase_26 | AC | 3,667 ms
115,476 KB |
testcase_27 | AC | 3,329 ms
115,544 KB |
testcase_28 | AC | 3,378 ms
115,420 KB |
testcase_29 | AC | 75 ms
79,260 KB |
testcase_30 | AC | 76 ms
79,328 KB |
ソースコード
from math import gcd def isprime(n): if n <= 1: return False elif n == 2: return True elif n % 2 == 0: return False A = [2, 325, 9375, 28178, 450775, 9780504, 1795265022] s = 0 d = n - 1 while d % 2 == 0: s += 1 d >>= 1 for a in A: if a % n == 0: return True x = pow(a, d, n) if x != 1: for t in range(s): if x == n - 1: break x = x * x % n else: return False return True def pollard(n): if n % 2 == 0: return 2 if isprime(n): return n f = lambda x:(x * x + 1) % n step = 0 while 1: step += 1 x = step y = f(x) while 1: p = gcd(y - x + n, n) if p == 0 or p == n: break if p != 1: return p x = f(x) y = f(f(y)) def primefact(n): if n == 1: return [] p = pollard(n) if p == n: return [p] left = primefact(p) right = primefact(n // p) left += right return sorted(left) def popcount(n): n = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555) n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333) n = (n & 0x0f0f0f0f0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f0f0f0f0f) n = (n & 0x00ff00ff00ff00ff) + ((n >> 8) & 0x00ff00ff00ff00ff) n = (n & 0x0000ffff0000ffff) + ((n >> 16) & 0x0000ffff0000ffff) n = (n & 0x00000000ffffffff) + ((n >> 32) & 0x00000000ffffffff) return n MOD = 998244353 n = int(input()) A = list(map(int, input().split())) ans = 0 dp = [0] * (10 ** 6 + 1) for a in A: lst = list(set(primefact(a))) l = len(lst) tot = 1 for bit in range(1, 1 << l): prod = 1 pm = -1 for i in range(l): if bit >> i & 1: prod *= lst[i] tot += dp[prod] tot %= MOD ans += tot ans %= MOD for bit in range(1, 1 << l): prod = 1 pm = -1 for i in range(l): if bit >> i & 1: pm *= -1 prod *= lst[i] dp[prod] += pm * tot dp[prod] %= MOD print(ans % MOD)