原题链接：Problem - 1632D - Codeforces
晚上复习的时候再补全~
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))int n;
const int N = 2e5 + 10;
ll a[N];
int Log[N];
ll st[N][21];void init(){
for (int i = 2; i <= N; ++i) //这里如果每组询问的n不一样，这里n就要换成NLog[i] = Log[i >> 1] + 1;//Log[i]表示log(i) stl log用多了会卡
}void solve( ) {for (int i = 1; i <= n; i++)st[i][0] = a[i];for (int j = 1; j <= 20; j++) { //这个地方的20是根据N的大小来定的(至少log2(N))for (int i = 1; i + (1 << j) - 1 <= n; i++) {st[i][j] = __gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);}}
}ll query(int l, int r) {int k = Log[r - l + 1];return __gcd(st[l][k], st[r - (1 << k) + 1][k]);
}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);init();solve();int pre = 1;int res = 0;rep(i, n){if(a[i] == 1){res++;pre = i + 1;}else{int l = pre, r = i;int flag = false;while(l < r){int mid = (l + r) >> 1;if(query(mid, i) >= i - mid + 1){r = mid;if(query(mid, i) == i - mid + 1){flag = true; break;}}else l = mid + 1;}if(query(l, i) == i - l + 1) flag = true;if(flag) res++, pre = i + 1;}printf("%d ", res);}return 0;
}