第十三届蓝桥杯Java、C++、Python组国赛真题——最大公约数（三语言AC）
给定一个数组, 每次操作可以选择数组中任意两个相邻的元素 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.输入格式输入的第一行包含一个整数 nn, 表示数组长度。
第二行包含 n n n 个整数 a 1 , a 2 , ⋯ , a n a_{1}, a_{2}, \cdots, a_{n} a1,a2,⋯,an 相邻两个整数之间用一个空格分隔。
2.输出格式输出一行包含一个整数, 表示最少操作次数。如果无论怎么操作都无法满 足要求, 输出 − 1 −1 −1 。
3.样例输入3
4 6 9
4.样例输出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.原题连接最大公约数
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表，不推荐写线段树，线段树常数太大。 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。
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; } 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)