蓝桥杯2022年第十三届决赛真题-最大公约数

解题思路:

我们需要找最小次数去得到 1，有 1之后顺着就可以把所有数变成 1，可以通过线段树维护区间最大公约数，然后通过二分求解最小次数

注意事项:

参考代码:

import java.util.*;

class Main {

    static final int N = 100009;

    static int n;

    static int[] a = new int[N];

    static int[] tr = new int[N << 2];

    static void build(int l, int r, int p) {

        if (l == r) {

            tr[p] = a[l];

            return;

        }

        int mid = l + ((r - l) >> 1);

        build(l, mid, p << 1);

        build(mid + 1, r, (p << 1) | 1);

        tr[p] = gcd(tr[p << 1], tr[(p << 1) | 1]);

    }

    static int query(int l, int r, int s, int t, int p) {

        int ans = 0;

        if (l >= s && r <= t) return tr[p];

        int mid = l + ((r - l) >> 1);

        if (mid >= s) ans = gcd(ans, query(l, mid, s, t, p << 1));

        if (mid < t) ans = gcd(ans, query(mid + 1, r, s, t, (p << 1) | 1));

        return ans;

    }

    static int gcd(int a, int b) {

        while (b != 0) {

            int tmp = a % b;

            a = b;

            b = tmp;

        }

        return a;

    }

    static void solve() {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        int cnt_one = 0;

        for (int i = 1; i <= n; i++) {

            a[i] = scanner.nextInt();

            if (a[i] == 1) cnt_one++;

        }

        if (cnt_one != 0) {

            System.out.println(n - cnt_one);

            return;

        }

        build(1, n, 1);

        int ans = Integer.MAX_VALUE;

        for (int i = 1; i <= n; i++) {

            int l = i, r = n;

            int cnt = Integer.MAX_VALUE;

            while (l <= r) {

                int mid = l + ((r - l) >> 1);

                if (query(1, n, i, mid, 1) == 1) {

                    cnt = mid - i;

                    r = mid - 1;

                } else {

                    l = mid + 1;

                }

            }

            ans = Math.min(ans, cnt);

        }

        if (ans == Integer.MAX_VALUE) {

            System.out.println(-1);

            return;

        }

        ans = ans + n - 1;

        System.out.println(ans);

    }

    public static void main(String[] args) {

        solve();

    }

}