問題一覧 > 通常問題

No.390 Longest Sequence

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 301
作問者 : ぴろず / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 486 / 自分の提出
問題文最終更新日: 2026-06-26 04:40:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 141 (順位表) の他の問題:

Problem Statement

You are given a non-empty set $S= \{ x_1,x_2, \dots ,x_N \}$ containing $N$ positive integers.
For $S$, a sequence $(a_1,a_2, \dots ,a_M)$ of length $M(\geq 1)$ is called "good" if it has the following $2$ properties.

  1. For every $i(1 \leq i \leq M)$, $a_i \in S$
  2. For every $i(1 \leq i \leq M - 1)$, $a_i < a_{i+1}$ and $a_{i+1}$ is a multiple of $a_i$

Write a program that finds the length of the longest "good" sequence.

Input

$N$
$x_1$ $x_2$ $\dots$ $x_N$

Line $1$ contains $N$.
Line $2$ contains $N$ space-separated integers $x_1,x_2, \dots ,x_N$.

$1 \leq N \leq 10^5$
$1 \leq x_i \leq 10^6 \; (1 \leq i \leq N)$
$x_i \neq x_j \; (1 \leq i < j \leq N)$

Output

Print the length of the longest "good" sequence on $1$ line. Print a newline at the end.

Sample

Sample 1
Input
5
1 2 3 4 5
Output
3

Examples of "good" sequences include $(1,2)$, $(2,4)$, and $(5)$.
The only "good" sequence of length $3$ is $(1,2,4)$, and this is the maximum.

Sample 2
Input
7
3 4 8 9 16 27 432
Output
4

There are $2$ "good" sequences of maximum length: $(3,9,27,432)$ and $(4,8,16,432)$.
Since the output is the maximum length of a "good" sequence, print $4$.

Sample 3
Input
7
1 2 22 88 8 4 440
Output
6

$x_1, x_2, \dots x_N$ may not be in ascending order.

Sample 4
Input
5
2 3 5 7 11
Output
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。