結果

問題 No.2075 GCD Subsequence
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:35:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,533 ms / 4,000 ms
コード長 1,815 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 135,648 KB
最終ジャッジ日時 2025-04-16 00:37:54
合計ジャッジ時間 34,321 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    max_A = 10**6
    min_prime = [0] * (max_A + 1)
    for i in range(2, max_A + 1):
        if min_prime[i] == 0:
            min_prime[i] = i
            for j in range(i * 2, max_A + 1, i):
                if min_prime[j] == 0:
                    min_prime[j] = i

    input = sys.stdin.read().split()
    n = int(input[0])
    A = list(map(int, input[1:n+1]))
    mod = 998244353
    total = 0
    cnt = defaultdict(int)

    for a in A:
        if a == 1:
            delta = 1
            total = (total + delta) % mod
            continue
        
        primes = set()
        x = a
        while x != 1:
            p = min_prime[x]
            primes.add(p)
            while x % p == 0:
                x = x // p
        
        if not primes:
            delta = 1
            total = (total + delta) % mod
            continue
        
        primes = list(primes)
        m = len(primes)
        sum_contribution = 0
        
        for mask in range(1, 1 << m):
            d = 1
            k = 0
            for i in range(m):
                if mask & (1 << i):
                    d *= primes[i]
                    k += 1
            sign = 1 if k % 2 == 1 else -1
            sum_contribution += sign * cnt.get(d, 0)
        
        sum_contribution %= mod
        prev_total = total
        mutual_prime_count = (prev_total - sum_contribution) % mod
        delta = (prev_total - mutual_prime_count + 1) % mod
        total = (total + delta) % mod
        
        for mask in range(1, 1 << m):
            d = 1
            for i in range(m):
                if mask & (1 << i):
                    d *= primes[i]
            cnt[d] = (cnt[d] + delta) % mod
    
    print(total % mod)

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