1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

class Solution {
public:
    int minStable(std::vector<int>& nums, int maxC) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        
        int logN = std::log2(n) + 1;
        std::vector<std::vector<int>> st(n, std::vector<int>(logN));
        for (int i = 0; i < n; ++i) {
            st[i][0] = nums[i];
        }
        for (int j = 1; j < logN; ++j) {
            for (int i = 0; i + (1 << j) <= n; ++i) {
                st[i][j] = std::gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
        
        auto GCD = [&](int L, int R) {
            int len = R - L + 1;
            int k = std::log2(len);
            return std::gcd(st[L][k], st[R - (1 << k) + 1][k]);
        };
        
        int left = 1, right = n;
        for (int mid = (left + right) / 2; right >= left; ) {
            bool valid = true;
            int ops = 0, i = 0;
            
            while (i <= n - mid) {
                int cm = GCD(i, i + mid - 1);
                if (cm > 1) {
                    ++ops;
                    if (ops > maxC) {
                        valid = false;
                        break;
                    }
                    i += mid;
                }
                else {
                    ++i;
                }
            }
            
            if (valid) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
            mid = (left + right) / 2;
        }
        
        return right;
    }
};