也会有发光的一天吖

# 转载自csdn上的大佬
```cpp
import java.util.Scanner;
 
public class _Test2 {
    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;    //统计数组中1的个数
        for (int i = 1; i <= n; ++i) {
            a[i] = sc.nextInt();
            if (a[i] == 1) f++;
        }
        
        if (f != 0) {
            System.out.println(n-f);
            return;
        }
        
        build(1, 1, n);
        
        if (query(1, 1, n) != 1) {
            System.out.println(-1);
            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);
        }
        System.out.println(n-1+ans);
    }
 
    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) {        //求区间gcd
        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;        //区间的最大公约数
        }
    }
}
```
# 参考资料： 
https://blog.csdn.net/qq_37419853/article/details/129163895

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

也会有发光的一天吖

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

线段树--蓝桥杯2022年第十三届决赛真题-最大公约数（C/C++/Java组）

评论区

精彩推荐

破解简单密码（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C二级辅导-同因查找（C语言代码）

IP判断（C语言代码）

矩形面积交（C语言代码）

交换Easy （C语言代码）

也会有发光的一天吖

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

线段树--蓝桥杯2022年第十三届决赛真题-最大公约数（C/C++/Java组）

评论区

精彩推荐

破解简单密码 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C二级辅导-同因查找 （C语言代码）

IP判断 （C语言代码）

矩形面积交 （C语言代码）

交换Easy （C语言代码）

　　评论区

破解简单密码（C语言代码）

C二级辅导-同因查找（C语言代码）

IP判断（C语言代码）

矩形面积交（C语言代码）