1.最大公约数

1.问题描述

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

2.输入格式

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

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

2.输出格式

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

3.样例输入

4 6 9

4.样例输出

5.数据范围

1≤n≤100000,1≤ai≤1091≤n≤100000,1≤a i ≤10^91≤n≤100000,1≤ai≤109

6.原题连接

最大公约数

2.解题思路

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

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

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

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

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

注意：Python语言运行较慢，推荐写成st表，不推荐写线段树，线段树常数太大。
时间复杂度O(nlogn)O(nlogn)O(nlogn)。

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(lint 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 mathdef 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] = afor j in range(1, exp + 1):for start in range(1, arr_len + 1):if start + (1 << j) - 1 > arr_len:breakdp[start][j] = gcd(dp[start][j - 1], dp[start + (1 << (j - 1))][j - 1])return dpdef 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 ** 9for i in range(1, n):l, r = i, nwhile l < r:mid = (l + r) >> 1if rmq_ask(dp, i, mid) == 1:r = midelse:l = mid + 1if rmq_ask(dp, i, r) == 1:ans = min(ans, r-i)print(ans + n-1)

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：春暖花开游人如织，热闹的济南五龙潭公园济南五龙潭公园介绍济南五龙潭春意盎然

下一篇：Spring项目的创建和使用-----实现代码解耦和自动化(直接用bean)

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

目录