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.
题目大意：给你一个长度为n的数组，每次可以进行一种操作把第i个数和第i+1个数的gcd替换为第i个数或者第i+1个数，问最少多少步能够使得序列全部变成1.
分析：对着样例手玩一下就能发现要先把其中的一个数变成1，再用这个1把其它的数全部变成1，关键就是怎么用最少的步数把其中的一个数变成1.我一开始的想法是找一对距离最近且gcd=1的数，借助中间的数把它们联系在一起.事实上这样是错的.比如42 35 15,这是可以变成1的，然而却找不到一对互素的数，再来考虑这个过程，并不需要两个数互素才行，可以把这两个数分别往中间传递，每次取gcd,这样枚举一个左端点和一个右端点判断一下gcd是否为1就好了.
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; const int inf = 0x7fffffff; int n, a[], minn = inf;
int flag = ; int gcd(int x, int y)
{
if (!y)
return x;
return gcd(y, x % y);
} int main()
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
if (a[i] == )
flag++;
}
int temp = a[];
for (int i = ; i <= n; i++)
temp = gcd(temp, a[i]);
if (temp != )
puts("-1");
else
if (flag)
printf("%d\n", n - flag);
else
{
for (int i = ; i <= n; i++)
{
int temp = a[i];
for (int j = i - ; j >= ; j--)
if ((temp = gcd(temp, a[j])) == )
{
minn = min(minn, i - j);
break;
}
temp = a[i];
for (int j = i + ; j <= n; j++)
if ((temp = gcd(a[i], a[j])) == )
{
minn = min(minn, j - i);
break;
}
}
printf("%d\n", minn + n - );
} return ;
}