|
||||||||||
Array-GiftTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1628 Accepted Submission(s): 356 Problem Description 最近开始流行赠送数组,所以 Beijixing 送给了 Liyishui 一个长度为 $n$ 的**正整数**序列 $a=[a_1,\dots,a_n]$,并附赠了两种操作: - 操作1:选择不同的下标 $i,j$(即 $1\leq i,j\leq n$,$i \neq j$),且 $a_j\neq 0$,然后将 $a_i $ 修改为 $ a_{i} \bmod a_{j} $ - 操作2:选择某个 $i$ 满足 $1 \leq i \leq n$ 和任意一个 **正整数** $x$ ,将 $a_{i} $ 修改为 $a_{i}+x$. Liyishui 喜欢倒腾数组,她希望只使用这两种操作让 $a$ 只剩 **恰好一个** 非 $0$ 数,其他的数都变成 $0$。两种操作均可使用任意次。不幸的是Liyishui最近忙着赶ddl,你能帮忙求出**最小操作次数**吗? Input 第一行输入一个正整数 $T$ ,表示一共有 $T$ 组测试用例,$ 1 \leq T \leq 30 $. 接下来每组测试用例由两行构成:其中第一行输入一个正整数 $ n(1 \leq n \leq 100) $ ,表示序列 $ a $ 的长度。第二行输入 $ n $ 个正整数 $ a_1,\dots,a_n $,相邻两数用一个空格隔开,表示序列 $ a $ . 对 $ 1\leq i\leq n $ ,有 $ 1\leq a_i\leq 10^6 $ . Output 对每个测试用例,输出一行一个整数,表示最小操作次数。 Sample Input
Sample Output
Hint 对于第一个样例,一种可能操作如下:$[2,3,5,7] \to [2, \mathbf{1},5,7] \to [ \mathbf{0},1,5,7] \to [0,1, \mathbf{0},7] \to [0,1,0, \mathbf{0}]$, 一共用了 $4$ 次操作,可以证明这是最少可能的操作次数。 对于第二个样例,一种可能操作如下:$[2,4,6,8] \to [2,\mathbf{0},6,8] \to [2,0,\mathbf{0},8] \to [2,0,0,\mathbf{0}]$, 一共用了 $3$ 次操作,可以证明这是最少可能的操作次数。 Source | ||||||||||
|