結果

問題 No.2075 GCD Subsequence
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:29:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,020 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 191,560 KB
最終ジャッジ日時 2025-03-31 17:30:53
合計ジャッジ時間 23,112 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def factor(n):
    primes_pows = []
    if n == 1:
        return primes_pows
    i = 2
    while i * i <= n:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            primes_pows.append((i, cnt))
        i += 1
    if n > 1:
        primes_pows.append((n, 1))
    return primes_pows

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    A = list(map(int, data[1:n+1]))
    
    div_counts = {}
    total = 0
    dp = {}
    
    for num in A:
        primes_pows = factor(num)
        primes = [p for p, e in primes_pows]
        k = len(primes)
        s = 0
        # Generate all non-empty subsets for inclusion-exclusion
        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]
            term = div_counts.get(m, 0)
            if bits % 2 == 1:
                s = (s + term) % MOD
            else:
                s = (s - term) % MOD
        s = s % MOD  # Ensure non-negative
        new_inc = (s + 1) % MOD
        # Update dp and total
        current_dp = dp.get(num, 0)
        dp[num] = (current_dp + new_inc) % MOD
        total = (total + new_inc) % MOD
        # Generate all divisors of the current number
        divisors = [1]
        for p, e in primes_pows:
            new_divisors = []
            for d in divisors:
                current_p_power = 1
                for _ in range(e + 1):
                    new_divisors.append(d * current_p_power)
                    current_p_power *= p
            divisors = new_divisors
        # Update div_counts
        for d in divisors:
            if d in div_counts:
                div_counts[d] = (div_counts[d] + new_inc) % MOD
            else:
                div_counts[d] = new_inc % MOD
    print(total % MOD)

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