結果

問題 No.2075 GCD Subsequence
ユーザー lam6er
提出日時 2025-04-16 16:24:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,072 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 81,404 KB
実行使用メモリ 128,336 KB
最終ジャッジ日時 2025-04-16 16:25:15
合計ジャッジ時間 14,343 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    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

    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    max_m = 10**6
    sum_d = [0] * (max_m + 2)
    answer = 0

    for num in a:
        if num == 1:
            dp_i = 1
            divisors = []
        else:
            factors = {}
            x = num
            while x > 1:
                p = spf[x]
                while x % p == 0:
                    factors[p] = factors.get(p, 0) + 1
                    x //= p
            primes = list(factors.keys())
            k = len(primes)
            sum_shared = 0
            for mask in range(1, 1 << k):
                bits = bin(mask).count('1')
                m = 1
                for i in range(k):
                    if mask & (1 << i):
                        m *= primes[i]
                sign = (-1) ** (bits + 1)
                term = sum_d[m] * sign
                sum_shared += term
                if sum_shared >= MOD or sum_shared <= -MOD:
                    sum_shared %= MOD
            sum_shared %= MOD
            dp_i = (1 + sum_shared) % MOD

            divisors = [1]
            for p in factors:
                exponents = factors[p]
                temp = []
                for d in divisors:
                    current = d
                    for _ in range(exponents):
                        current *= p
                        temp.append(current)
                divisors += temp
            divisors = list(set(divisors))
            if 1 in divisors:
                divisors.remove(1)
            divisors = [d for d in divisors if d != 1]

        for d in divisors:
            if d <= max_m:
                sum_d[d] = (sum_d[d] + dp_i) % MOD
        answer = (answer + dp_i) % MOD

    print(answer % MOD)

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