【传送门】Problem - D - Codeforces

大概题意就是，一个数组a，每一个区间gcd(区间左起l，右终于r)，当这个区间最大公约数 == r - l + 1 时，这个区间是boring 的，可以修改区间某值，使这个区间不boring， 求使这个数组任意区间都是不boring要修改几个值，然后按照到某位置要最少修改几个值输出。

解：

首先很容易想明白，如果一个区间是boring 的， 那么我们可以修改某个数为任意的大质数，要使数量最少，贪心下，然要修改的值尽量后。然后每个修改后的值就相当于一面墙。然后用st表来维护区间gcd

#include<bits/stdc++.h>
using namespace std;
const int N = 2000010;
int  a[N], mn[N], gd[N][22];int q, n;void init(){mn[0] = -1;for(int i = 1; i <= n; i++){mn[i] = ((i & (i - 1)) == 0) ? mn[i - 1] + 1 : mn[i - 1];gd[i][0] = a[i];}for(int j = 1; j <= mn[n]; j++){for(int i = 1; i + (1 << j) - 1 <= n; i++){gd[i][j] = __gcd(gd[i][j-1], gd[i + (1 << (j - 1) + 1)][j - 1]);}}
}
inline int qgd(int L, int R){int k = mn[R - L + 1];return __gcd(gd[L][k], gd[R - (1 << k) + 1][k]);
}signed main(){cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];init();int ans = 0;int maxr = -1;int pt = 0;for(int i = 0; i < n; i ++){while(pt < i && qgd(pt, i) < i - pt + 1) pt++;if(qgd(pt, i) == i - pt + 1){if(pt > maxr){++ans;maxr = i;}}cout << ans << " ";}
}