結果

問題 No.2075 GCD Subsequence
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:28:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,394 bytes
コンパイル時間 416 ms
コンパイル使用メモリ 82,476 KB
実行使用メモリ 141,552 KB
最終ジャッジ日時 2025-06-12 15:28:51
合計ジャッジ時間 17,594 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    MOD = 998244353
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N
    
    max_num = 10**6
    spf = list(range(max_num + 1))
    for i in range(2, int(max_num**0.5) + 1):
        if spf[i] == i:
            for j in range(i*i, max_num + 1, i):
                if spf[j] == j:
                    spf[j] = i

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

    cnt = defaultdict(int)
    answer = 0
    for num in A:
        primes = get_primes(num)
        k = len(primes)
        if k == 0:
            dp = 1
            answer = (answer + dp) % MOD
            continue
        
        m_list = []
        for mask in range(1, 1 << k):
            m = 1
            for j in range(k):
                if mask & (1 << j):
                    m *= primes[j]
            m_list.append(m)
        
        S = 0
        for m in m_list:
            bits = bin(mask).count('1')  # Wait, mask is not defined here. So need to track mask.
            # Alternative approach: for each (mask, m) pair, track the bits.
            # Alternatively, precompute bits for each mask.
            # To fix this, precompute the number of bits for each mask in m_list.
            # So, in the previous loop, store tuples (mask, m, bits)
            # But for efficiency, better precompute bits for each mask.

        # Rework the code to precompute bits for each mask in m_list
        m_list_with_bits = []
        for mask in range(1, 1 << k):
            bits = bin(mask).count('1')
            m = 1
            for j in range(k):
                if mask & (1 << j):
                    m *= primes[j]
            m_list_with_bits.append((m, bits))
        
        S = 0
        for m, bits in m_list_with_bits:
            sign = (-1) ** (bits + 1)
            sum_m = cnt.get(m, 0)
            S += sign * sum_m
        S %= MOD
        dp = (1 + S) % MOD
        answer = (answer + dp) % MOD
        
        for m, bits in m_list_with_bits:
            cnt[m] = (cnt[m] + dp) % MOD

    print(answer % MOD)

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