CodeForces Round 1028 (Div. 2)

🧮 C. Gellyfish and Flaming Peony

Time limit per test: 2 seconds
Memory limit per test: 512 megabytes

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

Gellyfish is given an array of n positive integers a₁, a₂, ..., aₙ.

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

Select two indices i, j such that 1 ≤ i, j ≤ n and i ≠ j.
Replace a[i] with gcd(a[i], a[j]).

Gellyfish asks you: What is the minimum number of operations required to make all elements equal?

Note: It can be proven that it’s always possible to make all elements equal using the allowed operations.

📥 Input

Each test contains multiple test cases.

The first line contains a single integer t — the number of test cases (1 ≤ t ≤ 5000).
For each test case:
- The first line contains an integer n (1 ≤ n ≤ 5000) — the size of the array.
- The second line contains n integers a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ 5000).

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

📤 Output

For each test case, output a single integer — the minimum number of operations to make all elements equal.

💡 Example

Input

3 3 12 20 30 6 1 9 1 9 8 1 3 6 14 15

Output

4 3 3

Solution

First we need to find gcd in the array. if any element is equal to gcd than we can simply pick a gcd element and non-gcd element and convert the non-gcd element to gcd element. answer will be number of non-gcd element in array. but problem arrise when there is no gcd element in array. In this case we need to create a gcd element in minimum operation.So wen need to find minimum steps to find gcd using smallest number of operation. We could do a bfs on gcd.

 1const int N = 5000 + 5;
 2int g[N][N];
 3
 4inline void precompute_gcd() {
 5    for(int x = 0; x < N; x++) 
 6        g[x][0] = g[0][x] = g[x][x] = x;
 7    for(int x = 1; x < N; x++)
 8        for(int y = 1; y < x; y++)
 9            g[x][y] = g[y][x] = g[y][x % y];
10}

Purpose: Quickly get gcd(x, y) for any x, y in [5000]. Why? To speed up repeated GCD calculations. eucledian algorithm gcd(x,y)=gcd(y,x%y)

we need to find gcd of entire array. Then we will gcd from every element in array. so that new gcd of array become 1. we can easily find steps to get gcd 1 in arrays.

If array contain gcd as one of the element we can easily get answer

1if(has_gcd) {
2    int cnt = 0;
3    for(int i = 1; i <= n; i++)
4        cnt += (a[i] != 1);
5    printf("%d\n", cnt);
6    return;
7}

If any element is already at the GCD, each other element can be reduced to GCD in one operation. So, answer is the number of elements not yet at GCD

When No element is gcd

 1memset(f, 0x3f, sizeof(f));
 2for(int i = 1; i <= n; i++)
 3    f[a[i]] = 0;
 4
 5for(int x = m; x >= 1; x--)
 6    for(int i = 1; i <= n; i++) {
 7        int y = a[i];
 8        int gcd_xy = g[x][y];
 9        if(f[x] + 1 < f[gcd_xy])
10            f[gcd_xy] = f[x] + 1;
11    }
12
13int ans = max(f[1] - 1, 0);
14for(int i = 1; i <= n; i++)
15    if(a[i] > 1) ans++;
16printf("%d\n", ans);

F[x] = minimum steps to reduce some number to x. Initialize f[a[i]] = 0 (starting points). As we can get elements in array in 0 Operations. All other f[x] are set to a large value (infinity). For each possible value x, try to combine with each a[i] to get gcd(x, a[i]), and update the minimum steps. The answer is the minimum steps to get to 1 (since after normalization, GCD is 1), adjusted for the number of elements. Here m is maximum element in array. after Nomalizing entire array. If we can reach x in f[x] steps, then we can reach gcd(x, y) in f[x] + 1 steps (one more operation).

Entire Code

 1#include<bits/stdc++.h>
 2using namespace std;
 3
 4const int N = 5000 + 5;
 5int g[N][N], f[N], a[N];
 6
 7inline void precompute_gcd() {
 8    for(int x = 0; x < N; x++) 
 9        g[x][0] = g[0][x] = g[x][x] = x;
10    for(int x = 1; x < N; x++)
11        for(int y = 1; y < x; y++)
12            g[x][y] = g[y][x] = g[y][x % y];
13}
14
15void solve() {
16    int n, m = 0, k = 0;
17    scanf("%d", &n);
18    for(int i = 1; i <= n; i++) {
19        scanf("%d", &a[i]);
20        k = g[k][a[i]]; // Compute overall GCD
21    }
22    
23    bool has_gcd = false;
24    for(int i = 1; i <= n; i++) {
25        if(a[i] == k) has_gcd = true;
26        a[i] /= k; // Normalize
27        m = max(m, a[i]);
28    }
29    
30    if(has_gcd) {
31        int cnt = 0;
32        for(int i = 1; i <= n; i++)
33            cnt += (a[i] != 1);
34        printf("%d\n", cnt);
35        return;
36    }
37    
38    memset(f, 0x3f, sizeof(f));
39    for(int i = 1; i <= n; i++)
40        f[a[i]] = 0;
41    
42    for(int x = m; x >= 1; x--)
43        for(int i = 1; i <= n; i++) {
44            int y = a[i];
45            int gcd_xy = g[x][y];
46            if(f[x] + 1 < f[gcd_xy])
47                f[gcd_xy] = f[x] + 1;
48        }
49    
50    int ans = max(f[1] - 1, 0);
51    for(int i = 1; i <= n; i++)
52        if(a[i] > 1) ans++;
53    printf("%d\n", ans);
54}
55
56int main() {
57    precompute_gcd();
58    int T;
59    scanf("%d", &T);
60    while(T--) solve();
61    return 0;
62}

#Codeforces