Codeforces Round 1028 (Div. 2) C. Gellyfish and Flaming Peony

Codeforces Round 1028 (Div. 2) C. Gellyfish and Flaming Peony

题目

Gellyfish hates math problems, but she has to finish her math homework:

Gellyfish is given an array of n n n positive integers a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1​,a2​,…,an​.

She needs to do the following two-step operation until all elements of a a a are equal:

1. Select two indexes i i i, j j j satisfying 1 ≤ i , j ≤ n 1 \leq i, j \leq n 1≤i,j≤n and i ≠ j i \neq j i=j.
2. Replace a i a_i ai​ with gcd ⁡ ( a i , a j ) \gcd(a_i, a_j) gcd(ai​,aj​).

Now, Gellyfish asks you for the minimum number of operations to achieve her goal.

It can be proven that Gellyfish can always achieve her goal.

Input

Each test contains multiple test cases. The first line contains the number of test cases t t t ( 1 ≤ t ≤ 5000 1 \le t \le 5000 1≤t≤5000). The description of the test cases follows.

The first line of each test case contains a single integer n n n ( 1 ≤ n ≤ 5000 1 \leq n \leq 5000 1≤n≤5000) — the length of the array.

The second line of each test case contains n n n integers a 1 , a 2 , … , a n a_1,a_2,\ldots,a_n a1​,a2​,…,an​ ( 1 ≤ a i ≤ 5000 1 \leq a_i \leq 5000 1≤ai​≤5000) — the elements of the array.

It is guaranteed that the sum of n n n over all test cases does not exceed 5000 5000 5000.

Output

For each test case, output a single integer — the minimum number of operations to achieve her goal.

题目解析及思路

题目要求不断执行操作，使数组所有元素相等，输出最少的操作数

操作：选择两个下标i,j，将a[i]替换为gcd(a[i],a[j])

样例输入

3
12 20 30

样例输出

4

代码

/*
不难想到，最终相同的数一定是所有元素的gcd，因此先求出这个最终数，如果他本身就存在，那么其他所有数变到最终数只需要一次操作，如果不存在，再考虑将某个元素变成这个最终数的最少次数
*/
#include 
#define endl '\n'
using namespace std;
void solve(){
    int n;
    cin>>n;
    vector a(n);
    //哈希表记录次数
    map mp;
    int g = 0;
    for(int &i:a){
        cin>>i;
        mp[i] ++;
        g = gcd(g,i);
    }
    //如果g本身存在，输出所有不为g的数的数量
    if(mp[g]){
        cout
        //x存在，操作数为0
        op[x] = 0;
        //枚举所有可能数与x求gcd
        for(int i=1;i
            int gg = gcd(i,x);
            op[gg] = min(op[gg],op[i] + 1);
        }
    }
    cout
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cint;
    while(t--){
        solve();
    }
}