第十三届蓝桥杯Java、C++、Python组国赛真题——最大公约数（三语言AC）

1.最大公约数

1.问题描述

给定一个数组, 每次操作可以选择数组中任意两个相邻的元素 $x,y$ 并将其 中的一个元素替换为 $\gcd (x,y)$, 其中 $\gcd (x,y)$ 表示 $x$ 和 $y$ 的最大公约数。 请问最少需要多少次操作才能让整个数组只含 1 。

2.输入格式

输入的第一行包含一个整数 $n$, 表示数组长度。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n$ 相邻两个整数之间用一个空格分隔。

2.输出格式

输出一行包含一个整数, 表示最少操作次数。如果无论怎么操作都无法满 足要求, 输出 $-1$ 。

3.样例输入

3

4 6 9

4.样例输出

4

5.数据范围

$1\le n\le 100000,1\le ai\le 10^9$

6.原题连接

最大公约数

2.解题思路

首先先考虑数组中是否存在$1$，如果数组中存在$1$，那么我们可以直接进行平铺把全部变成$1$，假设$1$的个数为$x$个，那么最终的答案应该是$n-x$次。

如果原数组中不存在$1$，该如何呢？那么我们应该想方法变出一个$1$，然后使用这个$1$进行平推将数组全部变成$1$。关于$gcd$，我们首先要明白——如果一段子数组的的$gcd$为$1$,那么原数组的$gcd$也一定为$1$。 这也非常容易理解，如果存在一个数组的$gcd$为$1$，那么这个数组无论再加上任何正整数，$gcd$也永远是$1$，因为$1$和任何数的$gcd$都是$1$。

题意要求最少次数，那么在没有$1$的情况下，我们需要使用最少的步数获得$1$，那么就是我们需要在数组中找到最短的子数组，使得它们的$gcd$为1。所以我们会涉及道查询区间$gcd$这个操作，直接暴力肯定不可取，所以我们应该联想到线段树来进行查询。

那么如何寻找最短的子数组满足区间$gcd$为$1$呢？我们可以考虑二分。对于数组中的每个数我们都可以固定为左端点$l$，然后去二分它的右端点，求出使得区间$[l,r]$的$gcd$为$1$的最小的右端点。既然二分就需要满足二段性,根据上一段的描述，我们可以知道,如果$[l,r]$的 $gcd$ 为$1$，那么$[l,r+1]...[l,n]$这些区间的$gcd$也一定为$1$,
而$[l,l+1]...[l,r-1]$这些区间却并不一定符合条件。这样每个数我们都定为左端点去二分它的右端点，所有答案取最小值就能找出$gcd$位$1$的最短区间。

当然我们如何判断无解的情况呢?还是根据上述$gcd$的理论知识，如果$[1,n]$的$gcd$都不为$1$，那么任何子数组的$gcd$也不可能为$1$，此时为无解。

注意：Python语言运行较慢，推荐写成st表，不推荐写线段树，线段树常数太大。不过任何语言都推荐写st表，代码较短
时间复杂度$O(nlo{g}^{2}n)$。

3.Ac_code

C++

#include
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N=100010;

int n;
int a[N];
struct node
{
    int l, r;
    int g;
}tr[N * 4];

void pushup(int u)
{
    tr[u].g =__gcd(tr[u<<1].g,tr[u<<1|1].g);
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, a[r]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].g;
    int mid = tr[u].l + tr[u].r >> 1;
    if(r<=mid) return query(u<<1,l,r);
    else if(l>mid) return query(u<<1|1,l,r);
    else return __gcd(query(u<<1,l,r),query(u<<1|1,l,r));
}
void solve()
{
	cin>>n;
	int f=0;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		if(a[i]==1) f++;
	}
	if(f){
		printf("%d\n",n-f);
		return;
	}
	build(1,1,n);
	if(query(1,1,n)!=1){
		puts("-1");
		return;
	}
	int ans=inf;
	for(int i=1;i<=n;++i){
		int l=i+1,r=n+1;
		while(l<r){
			int mid=l+r>>1;
			if(query(1,i,mid)==1) r=mid;
			else l=mid+1;
		}
		if(query(1,i,r)==1) ans=min(ans,r-i);
	}
	printf("%d\n",n-1+ans);
}
int main() 
{
	solve();
    return 0;
}
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

C++ ST表

#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

int n;
int f[N][21], Log2[N], b[N];
void build() {
	for (int i = 2; i <= n; ++i)
		Log2[i] = Log2[i / 2] + 1;
	for (int i = 1; i <= n; i++)
		f[i][0] = b[i];
	for (int i = 1; i <= 20; ++i)
		for (int j = 1; j + (1 << i) - 1 <= n; ++j)
			f[j][i] = __gcd(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
}
int query(int L, int R) {
	int s = Log2[R - L + 1];
	return __gcd(f[L][s], f[R - (1 << s) + 1][s]);
}
void solve()
{
	cin >> n;
	int f = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> b[i];
		if (b[i] == 1) f++;
	}
	//说明数组有 1 ,直接输出答案
	if (f) {
		cout << n - f << '\n';
		return;
	}
	build();
	//整个数组gcd不为1，无解
	if (query(1, n) != 1) {
		cout << -1 << '\n';
		return;
	}
	int ans = n;
	for (int i = 1; i <= n; ++i) {
		int l = i + 1, r = n + 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (query(i, mid) == 1) r = mid;
			else l = mid + 1;
		}
		if (query( i, r) == 1) ans = min(ans, r - i);
	}
	cout << n - 1 + ans << '\n';
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}
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

Java

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int N = 100010;
    static Node[] tr = new Node[N * 4];
    static int[] a = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int f = 0;
        for (int i = 1; i <= n; ++i) {
            a[i] = sc.nextInt();
            if (a[i] == 1) f++;
        }
        if (f != 0) {
            out.println(n - f);
            out.flush();
            return;
        }
        build(1, 1, n);
        if (query(1, 1, n) != 1) {
            out.println(-1);
            out.flush();
            return;
        }
        int ans = 0x3f3f3f3f;
        for (int i = 1; i <= n; ++i) {
            int l = i + 1, r = n + 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (query(1, i, mid) == 1) r = mid;
                else l = mid + 1;
            }
            if (query(1, i, r) == 1) ans = Math.min(ans, r - i);
        }
        out.println(n - 1 + ans);
        out.flush();
    }

    static int gcd(int a,int b){
        return b == 0 ? a:gcd(b,a%b);
    }

    static void pushup(int u) {
        tr[u].g = gcd(tr[u << 1].g, tr[u << 1 | 1].g);
    }

    static void build(int u, int l, int r) {
        if (l == r) tr[u] = new Node(l, r, a[r]);
        else {
            tr[u] = new Node(l, r, 0);
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }

    static int query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].g;
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else return gcd(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }

    static class Node {
        int l, r, g;

        public Node(int l, int r, int g) {
            this.l = l;
            this.r = r;
            this.g = g;
        }
    }
}
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

Pthon

from math import gcd
import math

def rmq_init(arr):
    arr_len = len(arr)
    exp = int(math.log(arr_len, 2))
    dp = [[0] * (exp + 1) for _ in range(arr_len + 1)]
    for i, a in enumerate(arr):
        dp[i + 1][0] = a
    for j in range(1, exp + 1):
        for start in range(1, arr_len + 1):
            if start + (1 << j) - 1 > arr_len:
                break
            dp[start][j] = gcd(dp[start][j - 1], dp[start + (1 << (j - 1))][j - 1])
    return dp

def rmq_ask(dp, left, right):  
    k = int(math.log(right - left + 1, 2))
    return gcd(dp[left][k], dp[right + 1 - (1 << k)][k])

n = int(input())
a = list(map(int, input().split()))


cnt1 = sum(ai == 1 for ai in a)
if cnt1 > 0:
    print(n - cnt1)
else:
    dp = rmq_init(a)
    if rmq_ask(dp, 1, n) != 1:
        print(-1)
    else:
        ans = 10 ** 9
        for i in range(1, n):
            l, r = i, n
            while l < r:
                mid = (l + r) >> 1
                if rmq_ask(dp, i, mid) == 1:
                    r = mid
                else:
                    l = mid + 1
            if rmq_ask(dp, i, r) == 1:
                ans = min(ans, r-i)
        print(ans + n-1)
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