結果

問題 No.2075 GCD Subsequence
ユーザー lam6er
提出日時 2025-04-16 16:32:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,597 ms / 4,000 ms
コード長 1,849 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 132,476 KB
最終ジャッジ日時 2025-04-16 16:33:54
合計ジャッジ時間 24,169 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict

def main():
    mod = 998244353
    input = sys.stdin.read().split()
    n = int(input[0])
    A = list(map(int, input[1:n+1]))
    
    max_A = 10**6
    lpf = list(range(max_A + 1))
    for i in range(2, int(max_A**0.5) + 1):
        if lpf[i] == i:
            for j in range(i*i, max_A + 1, i):
                if lpf[j] == j:
                    lpf[j] = i

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

    sum_p = defaultdict(int)
    ans = 0

    for x in A:
        if x == 1:
            ans = (ans + 1) % mod
            continue
        primes = get_primes(x)
        if not primes:
            ans = (ans + 1) % mod
            continue
        primes = sorted(primes)
        m = len(primes)
        masks = []
        for mask in range(1, 1 << m):
            product = 1
            bits = 0
            tmp = mask
            i = 0
            while tmp:
                if tmp & 1:
                    product *= primes[i]
                    bits += 1
                tmp >>= 1
                i += 1
            masks.append((product, bits))
        
        prev_sum = 0
        for product, bits in masks:
            sign = (-1) ** (bits + 1)
            prev_sum += sign * sum_p[product]
            if prev_sum >= mod or prev_sum <= -mod:
                prev_sum %= mod
        
        prev_sum %= mod
        contribution = (prev_sum + 1) % mod
        ans = (ans + contribution) % mod
        
        for product, _ in masks:
            sum_p[product] = (sum_p[product] + contribution) % mod

    print(ans % mod)

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