結果

問題 No.979 Longest Divisor Sequence
ユーザー lam6er
提出日時 2025-04-15 22:32:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,974 ms / 2,000 ms
コード長 678 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 121,300 KB
最終ジャッジ日時 2025-04-15 22:34:31
合計ジャッジ時間 4,334 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

n = int(input())
A = list(map(int, input().split()))

max_A = 3 * 10**5
dp = [0] * (max_A + 2)
max_length = 0

for x in A:
    current_max = 0
    if x != 1:
        sqrt_x = int(math.isqrt(x))
        for i in range(1, sqrt_x + 1):
            if x % i == 0:
                if i < x:
                    current_max = max(current_max, dp[i])
                counterpart = x // i
                if counterpart != i and counterpart < x:
                    current_max = max(current_max, dp[counterpart])
    new_length = current_max + 1
    if new_length > dp[x]:
        dp[x] = new_length
    if dp[x] > max_length:
        max_length = dp[x]

print(max_length)
0