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}a 1 ,a 2 ,⋯,a n 相邻两个整数之间用一个空格分隔。
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 ≤1 0 9
6.原题连接
首先先考虑数组中是否存在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 g c d，我们首先要明白—— 如果一段子数组的的g c d gcd g c d 为1 1 1,那么原数组的g c d gcd g c d 也一定为1 1 1 。 这也非常容易理解，如果存在一个数组的g c d gcd g c d为1 1 1，那么这个数组无论再加上任何正整数，g c d gcd g c d也永远是1 1 1， 因为1 1 1 和任何数的g c d gcd g c d 都是1 1 1 。
题意要求最少次数，那么在没有1 1 1的情况下，我们需要使用最少的步数获得1 1 1，那么就是我们需要在数组中找到最短的子数组，使得它们的g c d gcd g c d为1。所以我们会涉及道查询区间g c d gcd g c d这个操作，直接暴力肯定不可取，所以我们应该联想到线段树来进行查询。
那么如何寻找最短的子数组满足区间g c d gcd g c d为1 1 1呢？我们可以考虑 二分。对于数组中的每个数我们都可以固定为左端点l l l，然后去二分它的右端点，求出使得区间[ l , r ] [l,r][l ,r ]的g c d gcd g c d为1 1 1的 最小的右端点。既然二分就需要满足二段性,根据上一段的描述，我们可以知道,如果[ l , r ] [l,r][l ,r ]的 g c d gcd g c d 为1 1 1，那么[ l , r + 1 ] . . . [ l , n ] [l,r+1]…[l,n][l ,r +1 ]…[l ,n ]这些区间的g c d gcd g c d也一定为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 g c d位1 1 1的最短区间。
当然我们如何判断无解的情况呢?还是根据上述g c d gcd g c d的理论知识，如果[ 1 , n ] [1,n][1 ,n ]的g c d gcd g c d都不为1 1 1，那么任何子数组的g c d gcd g c d也不可能为1 1 1，此时为无解。
注意：Python语言运行较慢，推荐写成 st 表，不推荐写线段树，线段树常数太大。不过任何语言都推荐写 st 表，代码较短
时间复杂度O ( n l o g 2 n ) O(nlog^2n)O (n l o g 2 n )。
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(rmid) 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;in;++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;in;++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
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++;
}
if (f) {
cout << n - f << '\n';
return;
}
build();
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)
Original: https://blog.csdn.net/m0_57487901/article/details/127393669
Author: 执 梗
Title: 第十三届蓝桥杯Java、C++、Python组国赛真题——最大公约数（三语言AC）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/668859/
转载文章受原作者版权保护。转载请注明原作者出处！