提出 #52267196

---

ソースコード 拡げる

mod = 998244353


def fact(n):
    res = n
    a = []
    i = 2
    while i*i <= res:
        if res % i == 0:
            cnt = 0
            while res % i == 0:
                cnt += 1
                res //= i
            a.append((i, cnt))
        i += 1
    if res != 1:
        a.append((res, 1))
    return a


N, M = map(int, input().split())
A = list(map(int, input().split()))
f = fact(M)
K = len(f)
cnt = [0]*(1 << K)
for i in A:
    if M % i != 0:
        continue
    bit = 0
    for j in range(K):
        p, e = f[j]
        if i % (p**e) == 0:
            bit |= 1 << j
    cnt[bit] += 1

# ゼータ変換
for i in range(K):
    for j in range(1 << K):
        if (j >> i) & 1 == 0:
            cnt[j | (1 << i)] += cnt[j]

h = [pow(2, cnt[i], mod) for i in range(1 << K)]
# メビウス変換
for i in range(K):
    for j in range(1 << K):
        if (j >> i) & 1 == 0:
            h[j | (1 << i)] -= h[j]
            h[j | (1 << i)] %= mod

ans = h[(1 << K)-1]
if M == 1:
    ans -= 1
print(ans % mod)

提出情報

ジャッジ結果