結果

問題 No.2075 GCD Subsequence
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:38:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,704 bytes
コンパイル時間 669 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 138,024 KB
最終ジャッジ日時 2025-04-16 00:42:01
合計ジャッジ時間 17,541 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 2 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

max_a = 10**6
spf = list(range(max_a + 1))

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

def get_primes(x):
    primes = set()
    if x == 1:
        return primes
    while x != 1:
        p = spf[x]
        primes.add(p)
        while x % p == 0:
            x //= p
    return primes

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    a = list(map(int, input[1:n+1]))
    
    cnt = dict()
    ans = 0
    
    for num in a:
        primes = get_primes(num)
        if not primes:
            ans = (ans + 1) % MOD
            continue
        
        primes = sorted(primes)
        k = len(primes)
        sum_contribution = 0
        
        for mask in range(1, 1 << k):
            bits = bin(mask).count('1')
            product = 1
            for i in range(k):
                if mask & (1 << i):
                    product *= primes[i]
            if bits % 2 == 1:
                sum_contribution = (sum_contribution + cnt.get(product, 0)) % MOD
            else:
                sum_contribution = (sum_contribution - cnt.get(product, 0)) % MOD
        
        dp = (sum_contribution + 1) % MOD
        ans = (ans + dp) % MOD
        
        for mask in range(1, 1 << k):
            product = 1
            for i in range(k):
                if mask & (1 << i):
                    product *= primes[i]
            if product in cnt:
                cnt[product] = (cnt[product] + dp) % MOD
            else:
                cnt[product] = dp % MOD
    
    print(ans % MOD)

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