A16609 | Gellyfish and Flaming Peony
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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]$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？