CF2226B Everything Everywhere

当一个数组中最大值与最小值的差等于该数组所有元素的最大公约数（GCD）时，称该数组是“好数组”。注意，空数组不是好数组。 更正式地说，数组 $[a_1, a_2, \ldots, a_m]$ 是好数组当且仅当 $$ \max(a_1, a_2, \ldots, a_m) - \min(a_1, a_2, \ldots, a_m) = \gcd(a_1, a_2, \ldots, a_m)。 $$ 现在给定一个长度为 $n$ 的排列 $p$，请你计算该排列中有多少个好子数组。 *排列*是指长度为 $m$ 的数组，其中包含 $1$ 到 $m$ 的所有不同整数，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 就不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$m=3$，但有 $4$）。 *子数组*指的是数组 $a$ 的一个连续片段，也就是说，$b$ 可以通过删除 $a$ 开头若干项，以及末尾若干项（可以为零或全部）得到。特别地，数组自身也是自己的子数组。

每组测试包含多组测试用例。第一行为测试用例组数 $t$，满足 $1 \le t \le 10^4$。 每组测试的第一行是一个整数 $n$，表示排列 $p$ 的长度（$2 \le n \le 2 \cdot 10^5$）。 第二行为 $n$ 个整数 $p_1, p_2, \ldots, p_n$，表示排列 $p$（$1 \le p_i \le n$）。保证 $p$ 是排列。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示该排列中好子数组的数量。

对于第一个测试用例，只有一个好子数组，即 $[1, 2]$。 对于第二个测试用例，可以证明没有好子数组。 由 ChatGPT 5 翻译