問題一覧 > 通常問題

No.3345 Reducible Sequence

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 36
作問者 : MZKi / テスター : tassei903 jupiter_68 noya2
お気に入りにしたユーザー ProblemId : 9334 / 自分の提出
問題文最終更新日: 2025-11-13 17:50:54
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 作問ハッカソンコンテスト 003 Day1 (順位表) の他の問題:

Problem Statement

You are given a sequence $A$ of length $N$ consisting of positive integers.

Choose some elements from $A$ without choosing the same index more than once, and rearrange them to form a new sequence $B$ satisfying the following condition. Find the maximum possible length of $B$.

  • Let $M$ be the length of $B$. For every $i\ (1 \leq i \leq M)$, $B_i$ is a multiple of $i$.

Input

$N$
$A_1\ A_2\ \dots\ A_N$

  • $1 \le N \le 5000$
  • $1 \le A_i \le 5000\ (1 \le i \le N)$
  • All inputs are integers.

Output

Output the maximum possible length of $B$, followed by a newline.

Sample

Sample 1
Input
4
1 5 3 4
Output
3

$B = (1,4,3)$ has length $3$, and this is the longest.

Sample 2
Input
4
1 2 3 4
Output
4

$B = (1,2,3,4)$ has length $4$, and this is the longest. The longest $B$ may be equal to $A$.

Sample 3
Input
12
2 71 43 80 37 42 61 2 40 22 93 89
Output
6

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