NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
231 . 階梯序列
TopCoder
Tags
Description
對一個序列 $a_1,a_2,...,a_n$，找出最長的子序列 $a_{d_1},a_{d_2},...,a_{d_k}$ 滿足：
- $a_{d_i} = i\quad \forall 1\le i\le k$
- $d_i < d_{i + 1}\quad \forall 1\le i< k$
- $\gcd(d_i, d_{i+1}) > 1\quad \forall 1\le i < k$
Input Format
輸入第一行是一個正整數 $T$ 代表測資筆數。
在每筆測資中會先有一行一個正整數 $n$，接下來是一行 $n$ 個正整數 $a_i$。
- $1\le a_i\le n$
- 保證所有 $n$ 總和不超過 $3\times 10^ 5$。
Output Format
對每筆測資，輸出最長可能的長度。
Sample Input 1
4
4
1 2 3 4
4
2 2 3 4
5
1 1 2 2 3
7
1 1 2 2 4 3 4
4
1 2 3 4
4
2 2 3 4
5
1 1 2 2 3
7
1 1 2 2 4 3 4
Sample Output 1
1
0
2
3
0
2
3
Hints
Problem Source
IOICamp 2021 Day5 pF
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~14 | 無額外限制 | 100 |