CF1547F Array Stabilization (GCD version)

给定一个正整数数组 $a = [a_0, a_1, \dots, a_{n-1}]$（$n \ge 2$）。 每一步，你需要将数组 $a$ 替换为另一个长度为 $n$ 的数组，其中每个元素是相邻两个元素的最大公约数（即该元素本身与其右侧相邻元素的最大公约数；其中第 $n-1$ 个元素的右侧相邻元素为第 $0$ 个元素）。 形式化地说，从数组 $a = [a_0, a_1, \dots, a_{n-1}]$ 构造新数组 $b = [b_0, b_1, \dots, b_{n-1}]$，其中 $b_i = \gcd(a_i, a_{(i+1) \bmod n})$，$\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数，$x \bmod y$ 表示 $x$ 除以 $y$ 的余数。每一步都构造出数组 $b$，然后用 $b$ 替换 $a$（即执行 $a := b$）。 例如，如果 $a = [16, 24, 10, 5]$，那么 $b = [\gcd(16, 24), \gcd(24, 10), \gcd(10, 5), \gcd(5, 16)] = [8, 2, 5, 1]$。因此，经过一步操作后，$a = [16, 24, 10, 5]$ 变为 $[8, 2, 5, 1]$。 对于给定的数组 $a$，请你求出最少需要多少步才能使所有 $a_i$ 都相等（即 $a_0 = a_1 = \dots = a_{n-1}$）。如果原数组 $a$ 中所有元素本来就相等，则步数为 $0$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）。接下来有 $t$ 组测试数据。 每组测试数据包含两行。第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示序列 $a$ 的长度。第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$（$1 \le a_i \le 10^6$）。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出 $t$ 个数字，分别表示每组测试数据的答案。

由 ChatGPT 4.1 翻译