結果
問題 | No.2211 Frequency Table of GCD |
ユーザー |
|
提出日時 | 2023-02-10 21:56:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 973 ms / 2,000 ms |
コード長 | 4,325 bytes |
コンパイル時間 | 170 ms |
コンパイル使用メモリ | 82,440 KB |
実行使用メモリ | 108,012 KB |
最終ジャッジ日時 | 2024-07-07 17:59:19 |
合計ジャッジ時間 | 17,068 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
def gcd(a, b):while b: a, b = b, a % breturn adef isPrimeMR(n):d = n - 1d = d // (d & -d)L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]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 1def findFactorRho(n):m = 1 << n.bit_length() // 8for c in range(1, 99):f = lambda x: (x * x + c) % ny, r, q, g = 2, 1, 1, 1while 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 isPrimeMR(g): return gelif isPrimeMR(n // g): return n // greturn findFactorRho(g)def primeFactor(n):i = 2ret = {}rhoFlg = 0while i * i <= n:k = 0while n % i == 0:n //= ik += 1if k: ret[i] = ki += i % 2 + (3 if i % 3 == 1 else 1)if i == 101 and n >= 2 ** 20:while n > 1:if isPrimeMR(n):ret[n], n = 1, 1else:rhoFlg = 1j = 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 retdef divisors(N):pf = primeFactor(N)ret = [1]for p in pf:ret_prev = retret = []for i in range(pf[p]+1):for r in ret_prev:ret.append(r * (p ** i))return sorted(ret)def divisors_pf(pf):ret = [1]for p in pf:ret_prev = retret = []for i in range(pf[p]+1):for r in ret_prev:ret.append(r * (p ** i))return sorted(ret)def isPrime(n):if n in {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}: return 1if n <= 100: return 0for i in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]:if n % i == 0: return 0return isPrimeMR(n)def findPrime(n):if n <= 2: return 2i = n | 1while 1:if isPrime(i): return ii += 2def findNttFriendlyPrime(n, k, m=1):a = (n >> k) + 1i = (a << k) + 1while 1:if (i - 1) % m == 0:if isPrime(i):g = primitiveRoot(i)ig = pow(g, i - 2, i)return (i, g, ig) # p, g, invgi += 1 << kimport timeimport sys#sys.setrecursionlimit(500000)def I(): return int(sys.stdin.readline().rstrip())def MI(): return map(int,sys.stdin.readline().rstrip().split())def TI(): return tuple(map(int,sys.stdin.readline().rstrip().split()))def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))def S(): return sys.stdin.readline().rstrip()def LS(): return list(sys.stdin.readline().rstrip())#for i, pi in enumerate(p):from collections import defaultdict,dequeimport bisectimport itertoolsdic = defaultdict(int)def make_divisors(n):lower_divisors , upper_divisors = [], []i = 1while i*i <= n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n//i)i += 1return lower_divisors + upper_divisors[::-1]d = deque()N,M = MI()A = LI()mod = 998244353#たかいやつから数えるS = [0]*(M) #xで割り切れる個数for i in A:s = divisors(i)#make_divisors(i)for j in s:S[j-1] += 1ans = [0]*(M)for i in range(M-1,-1,-1):ans[i] = (ans[i]+pow(2,S[i],mod)-1)%mods = divisors(i+1)#make_divisors(i+1)for j in s:if i+1 == j:continueans[j-1] -= ans[i]for i in ans:print(i)