2 seconds
256 megabytes
standard input
standard output
You have an array a with length n, you can perform operations. Each operation is like this: choose two adjacent elements from a, say xand y, and replace one of them with gcd(x, y), where gcd denotes the greatest common divisor.
What is the minimum number of operations you need to make all of the elements equal to 1?
The first line of the input contains one integer n (1 ≤ n ≤ 2000) — the number of elements in the array.
The second line contains n space separated integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array.
Print -1, if it is impossible to turn all numbers to 1. Otherwise, print the minimum number of operations needed to make all numbers equal to 1.
5
2 2 3 4 6
5
4
2 4 6 8
-1
3
2 6 9
4
In the first sample you can turn all numbers to 1 using the following 5 moves:
- [2, 2, 3, 4, 6].
- [2, 1, 3, 4, 6]
- [2, 1, 3, 1, 6]
- [2, 1, 1, 1, 6]
- [1, 1, 1, 1, 6]
- [1, 1, 1, 1, 1]
We can prove that in this case it is not possible to make all numbers one using less than 5 moves.
这个题很简单，就是找一下那个公约数为1
看测试样例1：
2 2 3 4 6
先求他的第一层公约数就是2和2，2和3，3和4，4和6求公约数
2 2 3 4 6
2 1 1 2
这时候发现有1的存在
答案就是 当前的层数-1＋n-1 （n就是几个数） 因为有一个1就能把所有的都变成1
注意特判
2
1 1
这种的
丑陋的代码：
#include <iostream>
#include <cstdio>
using namespace std;
long long arr[2005][2005];
long long gcd(long long a,long long b);
int main()
{
long long n,i,j;
int flag = 0;
scanf("%lld",&n);
for(i = 0; i < n; ++i) {
scanf("%lld",arr[0]+i);
if(arr[0][i] == 1)
flag ++;
}
if(flag) {
printf("%lld\n",n-flag);
return 0;
}
for(i = 1; i <= n-1; ++i)
{
for(j = 0; j < n - i; ++j)
{
arr[i][j] = gcd(arr[i-1][j], arr[i-1][j+1]);
if(arr[i][j] == 1) {
printf("%lld\n",i+n-1);
return 0;
}
}
}
printf("-1\n");
}
long long gcd(long long a,long long b)
{
return b == 0?a:gcd(b,a%b);
}