题目内容

小 U 得到了一个长度为 $n$ 的正整数序列 $A = [a_1, a_2, \dots, a_n]$。她想要将序列切分成若干连续的子段，每个子段必须满足一个条件：该子段中所有元素的最大公约数不超过子段的长度。换言之，对于子段 $a_l, a_{l+1}, \dots, a_r$，若记 $g = \gcd(a_l, a_{l+1}, \dots, a_r)$，则须有 $g \le r - l + 1$。我们称这样的子段为 可行段。现在小 U 需要把整个序列划分成尽可能多的可行段，且要求这些段两两不交并恰好覆盖原数组的每个位置。请你求出最多能划分成多少个可行段。如果无论怎么划分都无法形成任何一个可行段，则认为无法划分。

数据规模与约定： 测试数据包含多组用例。单个测试用例中，序列长度 $n$ 满足 $1 \le n \le 2 \times 10^5$，序列中的元素均为不超过 $10^9$ 的正整数。所有测试用例的 $n$ 总和不超过 $2 \times 10^5$，用例组数 $T$ 满足 $1 \le T \le 10^4$。

输入描述

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。接下来依次描述每个测试用例，每个用例的格式如下： 第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示序列的长度。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写