题目内容

定义数组中的一个连续子数组为“和谐段”，当且仅当该子数组所有元素的最大公约数不超过它的长度。即对于子数组 $a_l, a_{l+1}, \dots, a_r$，若 $\gcd(a_l, a_{l+1}, \dots, a_r) \le r - l + 1$，则称其为和谐段。

现在给定一个长度为 $n$ 的正整数数组，请你从中选取尽可能多的互不相交的和谐段，求最多可以选取的段数。如果不存在任何和谐段，则需报告这一情况。

约束条件：设测试数据组数为 $T$，$T$ 不超过 $10^4$；所有测试数据中数组长度 $n$ 的总和不超过 $2 \times 10^5$；数组元素均为正整数且不超过 $10^9$。

输入描述

第一行输入一个整数 $T$，表示测试数据的组数。

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