孤独的数组

NC235684. 孤独的数组

描述

给出一个长度为 $n$ 的整数数组 $A$ ，分别为 $A_1,A_2,...,A_n$ 。牛牛可以对数组进行操作，每次操作选定一个下标 $i$ $(1\le i\le n)$ ，再确定一个整数 $k$ $(0<k<10^9)$ ，令 $A_i=A_i\times k$ 。牛牛想要知道，最少需要操作几次，才能让数组 $A$ 变成 "孤独的数组"。

”孤独的数组“ 定义：对于全部 $i\ (2\le i\le n)$ ， $gcd(A_{i-1},A_i)=1$ 。

如果无论怎么操作都无法让数组变成孤独的，输出 $-1$ 。

输入描述

第一行包括一个整数 $n$ $(2\le n\le 10^5)$ 表示数组的长度。

第二行包括 $n$ 个整数，分别表示 $A_1,A_2,...,A_n$ ， $(1\le A_i\le 10^9)$ 。

输出描述

输出一行，包含一个整数，表示最小的操作次数。

示例1

输入:

2
1 2

输出:

说明:

$gcd(1,2)=1$ ，无需再操作。

示例2

输入:

2
2 2

输出:

-1

说明:

无论怎么操作都无法让 $gcd(A_1,A_2)=1$ ，输出 $-1$ 。

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3 解法, 执行用时: 113ms, 内存消耗: 15928K, 提交时间: 2023-08-13 13:55:35

import sys,math
n=int(input())
a=list(map(int,input().split()))
r=0
for i in range(1,n):
    if math.gcd(a[i-1],a[i]) !=1:
        r=-1
        break
print(r)