A16609. Gellyfish and Flaming Peony
编程题
普及/提高-
知识点
题目描述
Gellyfish 讨厌数学题，但她必须完成她的数学作业：
Gellyfish 得到一个包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 的数组。
她需要反复进行以下两步操作，直到数组 $a$ 的所有元素都相等为止：
1. 选择两个下标 $i$、$j$，满足 $1 \leq i, j \leq n$ 且 $i \neq j$。
2. 用 $\gcd(a_i, a_j)$ 替换 $a_i$ 的值。
现在，Gellyfish 想知道，最少需要多少次操作才能实现目标。
可以证明，Gellyfish 总是能够实现目标。
Gellyfish 得到一个包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 的数组。
她需要反复进行以下两步操作，直到数组 $a$ 的所有元素都相等为止：
1. 选择两个下标 $i$、$j$，满足 $1 \leq i, j \leq n$ 且 $i \neq j$。
2. 用 $\gcd(a_i, a_j)$ 替换 $a_i$ 的值。
现在，Gellyfish 想知道，最少需要多少次操作才能实现目标。
可以证明，Gellyfish 总是能够实现目标。
输入格式
每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 5000$），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示数组的长度。
每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 5000$），表示数组的元素。
保证所有测试用例中 $n$ 的总和不超过 $5000$。
每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示数组的长度。
每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 5000$），表示数组的元素。
保证所有测试用例中 $n$ 的总和不超过 $5000$。
输出格式
对于每个测试用例，输出一个整数，表示实现目标所需的最小操作次数。
输入输出样例
输入 #1
3 3 12 20 30 6 1 9 1 9 8 1 3 6 14 15
输出 #1
4 3 3
说明/提示
在第一个测试用例中，以下是一种最小化操作次数的方法：
1. 选择 $i = 3$，$j = 2$，用 $\gcd(a_3,a_2) = \gcd(30, 20) = 10$ 替换 $a_3$，此时 $a$ 变为 $[12, 20, 10]$。
2. 选择 $i = 1$，$j = 3$，用 $\gcd(a_1,a_3) = \gcd(12, 10) = 2$ 替换 $a_1$，此时 $a$ 变为 $[2, 20, 10]$。
3. 选择 $i = 2$，$j = 1$，用 $\gcd(a_2,a_1) = \gcd(20, 2) = 2$ 替换 $a_2$，此时 $a$ 变为 $[2, 2, 10]$。
4. 选择 $i = 3$，$j = 1$，用 $\gcd(a_3,a_1) = \gcd(10, 2) = 2$ 替换 $a_3$，此时 $a$ 变为 $[2, 2, 2]$。
1. 选择 $i = 3$，$j = 2$，用 $\gcd(a_3,a_2) = \gcd(30, 20) = 10$ 替换 $a_3$，此时 $a$ 变为 $[12, 20, 10]$。
2. 选择 $i = 1$，$j = 3$，用 $\gcd(a_1,a_3) = \gcd(12, 10) = 2$ 替换 $a_1$，此时 $a$ 变为 $[2, 20, 10]$。
3. 选择 $i = 2$，$j = 1$，用 $\gcd(a_2,a_1) = \gcd(20, 2) = 2$ 替换 $a_2$，此时 $a$ 变为 $[2, 2, 10]$。
4. 选择 $i = 3$，$j = 1$，用 $\gcd(a_3,a_1) = \gcd(10, 2) = 2$ 替换 $a_3$，此时 $a$ 变为 $[2, 2, 2]$。