結果

問題 No.2075 GCD Subsequence
ユーザー gew1fw
提出日時 2025-06-12 20:37:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,221 ms / 4,000 ms
コード長 3,242 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 245,648 KB
最終ジャッジ日時 2025-06-12 20:38:15
合計ジャッジ時間 34,543 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations
from collections import defaultdict

MOD = 998244353

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    if not A:
        print(0)
        return
    
    max_A = max(A)
    max_spf = max(2, max_A)
    
    # Precompute smallest prime factors (SPF)
    spf = list(range(max_spf + 1))
    for i in range(2, int(max_spf ** 0.5) + 1):
        if spf[i] == i:
            for j in range(i * i, max_spf + 1, i):
                if spf[j] == j:
                    spf[j] = i
    
    # Precompute Möbius function
    is_square_free = [True] * (max_spf + 1)
    for x in range(2, max_spf + 1):
        current = x
        factors = []
        while current > 1:
            p = spf[current]
            if current % p == 0:
                count_p = 0
                while current % p == 0:
                    current = current // p
                    count_p += 1
                if count_p > 1:
                    is_square_free[x] = False
                    break
                factors.append(p)
        if not is_square_free[x]:
            continue
    
    mu = [1] * (max_spf + 1)
    for x in range(2, max_spf + 1):
        if is_square_free[x]:
            current = x
            factors = []
            while current > 1:
                p = spf[current]
                factors.append(p)
                while current % p == 0:
                    current = current // p
            k = len(factors)
            mu[x] = (-1) ** k
        else:
            mu[x] = 0

    # Function to compute square-free divisors for x
    def get_square_free_divisors(x):
        if x == 1:
            return [1]
        current = x
        primes = []
        seen = set()
        while current > 1:
            p = spf[current]
            if p not in seen:
                primes.append(p)
                seen.add(p)
            while current % p == 0:
                current = current // p
        divisors = [1]
        for i in range(1, len(primes) + 1):
            for subset in combinations(primes, i):
                product = 1
                for p in subset:
                    product *= p
                divisors.append(product)
        return divisors

    # Precompute square-free divisors for each element in A
    square_free_divisors = []
    for x in A:
        divisors = get_square_free_divisors(x)
        square_free_divisors.append(divisors)
    
    # DP processing
    cnt = defaultdict(int)
    total_sum = 0
    result = 0
    for i in range(N):
        x = A[i]
        divisors = square_free_divisors[i]
        sum_coprimes = 0
        for d in divisors:
            if d > max_spf or mu[d] == 0:
                continue
            sum_coprimes += mu[d] * cnt[d]
            sum_coprimes %= MOD
        dp_i = (total_sum - sum_coprimes) % MOD
        dp_i = (dp_i + 1) % MOD
        
        for d in divisors:
            if d > max_spf:
                continue
            cnt[d] = (cnt[d] + dp_i) % MOD
        
        total_sum = (total_sum + dp_i) % MOD
        result = (result + dp_i) % MOD
    
    print(result % MOD)

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