結果
問題 | No.2578 Jewelry Store |
ユーザー |
|
提出日時 | 2023-01-13 17:55:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,066 ms / 3,500 ms |
コード長 | 3,360 bytes |
コンパイル時間 | 438 ms |
コンパイル使用メモリ | 82,512 KB |
実行使用メモリ | 137,260 KB |
最終ジャッジ日時 | 2024-09-27 00:36:47 |
合計ジャッジ時間 | 18,068 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 54 |
ソースコード
import sysfrom typing import Listfrom math import gcdinput = sys.stdin.readline# https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98class PrimeFactorize:@staticmethoddef __isPrimeMR(n: int):d = n - 1d = d // (d & -d)L = [2]for a in L:t = dy = pow(a, t, n)if y == 1: continuewhile y != n - 1:y = (y * y) % nif y == 1 or t == n - 1: return 0t <<= 1return 1@staticmethoddef __findFactorRho(n: int):m = 1 << n.bit_length() // 8for c in range(1, 99):f = lambda x: (x * x + c) % ny, r, q, g = 2, 1, 1, 1x = ys = ywhile g == 1:x = yfor i in range(r):y = f(y)k = 0while k < r and g == 1:ys = yfor i in range(min(m, r - k)):y = f(y)q = q * abs(x - y) % ng = gcd(q, n)k += mr <<= 1if g == n:g = 1while g == 1:ys = f(ys)g = gcd(abs(x - ys), n)if g < n:if PrimeFactorize.__isPrimeMR(g): return gelif PrimeFactorize.__isPrimeMR(n // g): return n // greturn PrimeFactorize.__findFactorRho(g)@staticmethoddef primeFactor(n):i = 2ret = {}rhoFlg = 0while i*i <= n:k = 0while n % i == 0:n //= ik += 1if k: ret[i] = ki += 1 + i % 2if i == 101 and n >= 2 ** 20:while n > 1:if PrimeFactorize.__isPrimeMR(n):ret[n], n = 1, 1else:rhoFlg = 1j = PrimeFactorize.__findFactorRho(n)k = 0while n % j == 0:n //= jk += 1ret[j] = kif n > 1: ret[n] = 1if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}return retP = 998244353t, m = map(int, input().split())pf = PrimeFactorize.primeFactor(m).keys()k = len(pf)parity = [(-1) ** bin(s).count('1') for s in range(1 << k)]def supset_zeta_product(f: List[int]):block = 1while block < 1 << k:offset = 0while offset < 1 << k:for i in range(offset, offset + block):f[i] = f[i + block] * f[i] % Poffset += 2 * blockblock <<= 1def solve():_, x0, c, d = map(int, input().split())prod = [1] * (1 << k)wi = x0for ai in map(int, input().split()):q, r = divmod(m, ai)if r == 0:t = 0for j, p in enumerate(pf):t |= (q % p == 0) << jprod[t] = prod[t] * (1 + wi) % Pwi = (c * wi + d) % Psupset_zeta_product(prod)ans = 0for s in range(1 << k):ans += parity[s] * prod[s]if m == 1:ans -= 1print(ans % P)for _ in range(t):solve()