CodeForces 891 A. Pride

Posted on | In , , | Comments:
| 7.6k | 7 mins.

http://codeforces.com/problemset/problem/891/A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

long long dp[2005][2005]; // dp[x][y]表示gcd(x...(x + y))
/*
x是起始点位置,y是距离
a1, a2, a3, a4, a5, a6, a7, a8
	↑	←	y	→	↑
	x				x + y
*/

// gcd(a1, a2, a3) = gcd(gcd(a1, a2), a3) = gcd(gcd(a1, a2), gcd(a2, a3))
// 所以

// 状态方程
// dp[x][y] = gcd(dp[x][y - 1], dp[x + 1][y - 1])

long long gcd(long long a, long long b) {
	while (1) {
		a = a % b;
		if (!a) {
			return b;
		}
		b = b % a;
		if (!b) {
			return a;
		}
	}
}

int main(int argc, char const *argv[])
{
	int n;
	int ones = 0;
	scanf("%d", &n);

	for (int x = 0; x < n; x++) {
		scanf("%lld", dp[x]);
		if (dp[x][0] == 1) {
			ones++;
		}

		// printf("%lld\t", dp[x][0]);
	}

	// printf("\n");

	if (ones) {
		printf("%d\n", n - ones);
		return 0;
	}

	for (int y = 1; y < n; y++) {//跨度距离从1开始
		for (int x = 0; x + y < n; x++) {//起始位置从x开始

			dp[x][y] = gcd(dp[x][y - 1], dp[x + 1][y - 1]);

			// printf("%lld\t", dp[x][y]);

			if (dp[x][y] == 1) {
				// printf("\n");
				printf("%d\n", n + y - 1);
				return 0;
			}

		}
	}

	printf("-1\n");
	return 0;

/**
*	
*	in:
*	
*	5
*	2 2 3 4 6
*	
*	out:
*	
*	2		2		3		4		6
*	↑↗		↑↗
*	2		1
*	
*	result：
*	
*	5
*	
*	
*/

}