231 . 階梯序列

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

63.6% (7/11)

Tags

ioicamp ioicamp-2021

Description

對一個序列 a1,a2,...,an，找出最長的子序列 ad1,ad2,...,adk 滿足：

  • adi=i∀1≤i≤k
  • di<di+1∀1≤i<k
  • gcd(di,di+1)>1∀1≤i<k

Input Format

輸入第一行是一個正整數 T 代表測資筆數。

在每筆測資中會先有一行一個正整數 n，接下來是一行 n 個正整數 ai。

  • 1≤ai≤n
  • 保證所有 n 總和不超過 3×105。

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

Sample Output 1

1
0
2
3

Hints

Problem Source

IOICamp 2021 Day5 pF

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~14 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
Submit
Back to Top