Bestie (Codeforces 1732A)
Tags: Math, combinatorics

You are given an array $$$a$$$ consisting of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Friends asked you to make the greatest common divisor (GCD) of all numbers in the array equal to $$$1$$$. In one operation, you can do the following: Select an arbitrary index in the array $$$1 \leq i \leq n$$$; Make $$$a_i = \gcd(a_i, i)$$$, where $$$\gcd(x, y)$$$ denotes the GCD of integers $$$x$$$ and $$$y$$$. The cost of such an operation is $$$n - i + 1$$$.You need to find the minimum total cost of operations we need to perform so that the GCD of the all array numbers becomes equal to $$$1$$$.

Input: Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5\,000$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 20$$$) — the length of the array.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array.

Output: For each test case, output a single integer — the minimum total cost of operations that will need to be performed so that the GCD of all numbers in the array becomes equal to $$$1$$$.We can show that it's always possible to do so.

Note: In the first test case, the GCD of the entire array is already equal to $$$1$$$, so there is no need to perform operations.In the second test case, select $$$i = 1$$$. After this operation, $$$a_1 = \gcd(2, 1) = 1$$$. The cost of this operation is $$$1$$$.In the third test case, you can select $$$i = 1$$$, after that the array $$$a$$$ will be equal to $$$[1, 4]$$$. The GCD of this array is $$$1$$$, and the total cost is $$$2$$$.In the fourth test case, you can select $$$i = 2$$$, after that the array $$$a$$$ will be equal to $$$[3, 2, 9]$$$. The GCD of this array is $$$1$$$, and the total cost is $$$2$$$.In the sixth test case, you can select $$$i = 4$$$ and $$$i = 5$$$, after that the array $$$a$$$ will be equal to $$$[120, 60, 80, 4, 5]$$$. The GCD of this array is $$$1$$$, and the total cost is $$$3$$$.

Sample Inputs:
9
1
1
1
2
2
2 4
3
3 6 9
4
5 10 15 20
5
120 60 80 40 80
6
150 90 180 120 60 30
6
2 4 6 9 12 18
6
30 60 90 120 125 125

Sample Outputs:
0
1
2
2
1
3
3
0
1

Solution (Python):
import math
aa = []
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    c = l[0]
    for i in range(1, n):
        c = math.gcd(c, l[i])
    if n == 1:
        if l[0] == 1:
            aa.append(0)
        else:
            aa.append(1)
    elif c == 1:
        aa.append(0)
    elif math.gcd(c, n) == 1:
        aa.append(1)
    elif math.gcd(c, n - 1) == 1:
        aa.append(2)
    else:
        aa.append(3)
for i in aa:
    print(i)

Solution (Python):
import sys
from math import gcd
rd = sys.stdin.readline
for _ in range(int(rd())):
    n = int(rd())
    l = list(map(int, rd().split()))
    g = l[0]
    for i in l:
        g = gcd(i, g)
    if g == 1:
        print(0)
    else:
        x = gcd(l[-1], n)
        try:
            y = gcd(l[-2], n - 1)
        except:
            pass
        if gcd(g, x) == 1:
            print(1)
        elif gcd(g, y) == 1:
            print(2)
        else:
            print(3)

Solution (Python):
t = int(input())
arrlengths = []
arrvalues = []
gcdLast = 0
gcdPenultimate = 0

def findgcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x
for i in range(0, t):
    arrlengths.append(int(input()))
    arrvalues.append(list(map(int, input().split())))
for i in range(0, t):
    l = arrlengths[i]
    array = arrvalues[i]
    if l == 1:
        if array[0] == 1:
            print('0')
        else:
            print('1')
    else:
        gcd = findgcd(array[0], array[1])
        for j in range(2, l):
            gcd = findgcd(gcd, array[j])
            if j == l - 3:
                gcdPenultimate = gcd
            elif j == l - 2:
                gcdLast = gcd
            if gcd == 1:
                break
        if l == 2:
            gcdLast = array[0]
        elif l == 3:
            gcdLast = findgcd(array[0], array[1])
            gcdPenultimate = array[0]
        elif l == 4:
            gcdPenultimate = findgcd(array[0], array[1])
        if gcd == 1:
            print('0')
        else:
            tempgcd = findgcd(l, array[l - 1])
            if findgcd(tempgcd, gcdLast) == 1:
                print('1')
            else:
                tempgcd = findgcd(l - 1, array[l - 2])
                temp1gcd = findgcd(tempgcd, gcdPenultimate)
                if findgcd(temp1gcd, array[l - 1]) == 1:
                    print(2)
                else:
                    print('3')