結果

問題 No.2075 GCD Subsequence
コンテスト
ユーザー lam6er
提出日時 2025-03-20 19:03:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,478 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 139,116 KB
最終ジャッジ日時 2025-03-20 19:04:20
合計ジャッジ時間 49,325 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

MOD = 998244353

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    a = list(map(int, input[1:n+1]))

    if not a:
        print(0)
        return

    max_factor = max(a)
    sieve = list(range(max_factor + 1))

    for i in range(2, int(max_factor**0.5) + 1):
        if sieve[i] == i:
            for j in range(i * i, max_factor + 1, i):
                if sieve[j] == j:
                    sieve[j] = i

    def factor(x):
        if x == 1:
            return []
        factors = set()
        while x > 1:
            p = sieve[x]
            factors.add(p)
            while x % p == 0:
                x //= p
        return sorted(factors)

    f = defaultdict(int)
    total_sum = 0

    for num in a:
        factors = factor(num)
        m = len(factors)
        subsets = []

        for mask in range(1, 1 << m):
            bits = bin(mask).count('1')
            d = 1
            for i in range(m):
                if mask & (1 << i):
                    d *= factors[i]
            subsets.append((d, bits))

        sum_valid = 0
        for d, bits in subsets:
            sign = (-1) ** (bits + 1)
            sum_valid = (sum_valid + sign * f[d]) % MOD

        current = (sum_valid + 1) % MOD
        total_sum = (total_sum + current) % MOD

        for d, _ in subsets:
            f[d] = (f[d] + current) % MOD

    print(total_sum % MOD)

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