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

红太狼 2023-09-28 23:16 5阅读 0赞

#### 目录 ####

*  1.最大公约数
 *   *  1.问题描述
     *  2.输入格式
     *  2.输出格式
     *  3.样例输入
     *  4.样例输出
     *  5.数据范围
     *  6.原题连接
 *  2.解题思路
 *  3.Ac\_code
 *   *  C++
     *  Java
     *  Pthon

## 1.最大公约数 ##

### 1.问题描述 ###

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

### 2.输入格式 ###

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

第二行包含  n n n 个整数  a 1 , a 2 , ⋯   , a n a\_\{1\}, a\_\{2\}, \\cdots, a\_\{n\} a1,a2,⋯,an 相邻两个整数之间用一个空格分隔。

### 2.输出格式 ###

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

### 3.样例输入 ###

4 6 9

### 4.样例输出 ###

### 5.数据范围 ###

1 ≤ n ≤ 100000 , 1 ≤ a i ≤ 1 0 9 1≤n≤100000,1≤a i ≤10^9 1≤n≤100000,1≤ai≤109

### 6.原题连接 ###

[最大公约数][Link 1]

## 2.解题思路 ##

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

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

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

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

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

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

## 3.Ac\_code ##

### C++ ###

#include<bits/stdc++.h>
    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;
    }

**C++ ST表**

#include<bits/stdc++.h>
    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;
    }

### 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;
            }
        }
    }

### 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)

[Link 1]: https://www.lanqiao.cn/problems/2172/learning/