結果

問題 No.2211 Frequency Table of GCD
コンテスト
ユーザー meruuu61779999
提出日時 2023-02-10 21:54:16
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 785 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 166,708 KB
最終ジャッジ日時 2024-07-07 16:08:38
合計ジャッジ時間 5,498 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import defaultdict

inputs = sys.stdin.readline

"""再帰関数のときセット
sys.setrecursionlimit(10**7)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
"""

MOD = 998244353


def main():
    N, M = map(int, inputs().split())
    A = list(map(int, inputs().split()))
    after_dic = defaultdict(int)

    for a in A:
        before_dic, after_dic = after_dic, defaultdict(int)
        for GCD, cnt in before_dic.items():
            after_dic[GCD] += cnt
            after_dic[GCD] %= MOD
            GCD2 = math.gcd(GCD, a)
            after_dic[GCD2] += cnt
            after_dic[GCD2] %= MOD
        after_dic[a] += 1

    for i in range(1, M + 1):
        print(after_dic[i] % MOD)


if __name__ == '__main__':
    main()
0