結果

問題 No.2211 Frequency Table of GCD
ユーザー lam6er
提出日時 2025-03-20 21:11:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 172 ms / 2,000 ms
コード長 1,163 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 110,188 KB
最終ジャッジ日時 2025-03-20 21:11:31
合計ジャッジ時間 5,934 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

N, M = map(int, input().split())
A = list(map(int, input().split()))

# Step 1: Compute the frequency array cnt
cnt = [0] * (M + 1)
for x in A:
    cnt[x] += 1

# Step 2: Compute c[d] for each d, which is the count of elements divisible by d
c = [0] * (M + 1)
for d in range(1, M + 1):
    for m in range(d, M + 1, d):
        c[d] += cnt[m]

# Precompute powers of 2 up to the maximum possible c[d] (which is N)
max_pow = max(c)
pow2 = [1] * (max_pow + 1)
for i in range(1, max_pow + 1):
    pow2[i] = (pow2[i - 1] * 2) % MOD

# Step 3: Compute g[d] = 2^c[d] - 1 mod MOD
g = [0] * (M + 1)
for d in range(1, M + 1):
    if c[d] == 0:
        gd = 0
    else:
        gd = (pow2[c[d]] - 1) % MOD
    g[d] = gd

# Step 4: Compute f[d] using inclusion-exclusion by processing d in reverse order
f = [0] * (M + 1)
for d in range(M, 0, -1):
    sum_multiples = 0
    m = 2 * d
    while m <= M:
        sum_multiples = (sum_multiples + f[m]) % MOD
        m += d
    f[d] = (g[d] - sum_multiples) % MOD
    # Ensure non-negative
    if f[d] < 0:
        f[d] += MOD

# Output the result for each k from 1 to M
for k in range(1, M + 1):
    print(f[k])
0