题目描述

给定正整数序列 $h_1,\ldots,h_n$。

对于区间 $[l,r]$，我们称 $i$（$l\le i\le r$）关于 $[l,r]$ 是 好的，当且仅当：$h_i=\gcd(h_l,h_{l+1},\ldots,h_r)$。

对于 $i$，定义 $f(i)$ 表示：所有 $i$ 关于 $[l,r]$ 是好的区间中，$r-l+1$ 的最大值。

对于 $i=1,2,\ldots,n$，求出 $f(i)$。

$n \le 10^6$

题目分析

利用 ST 表我们可以做到以 $O(1)$ 的代价查询区间最大公约数。

现在，我们考虑区间 $[i, r]$ 的区间元素最大公约数是 $h_i$，$r$ 的最大值。$r$ 显然具有单调性，可以二分求出 $r$ 的最大值。同理可求得区间 $[l, i]$ 中 $l$ 的最小值。

时间复杂度 $O(n\log n)$

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n, h[N];
int f[N][20];

int query(int x, int y) {
  int k = log(y - x + 1) / log(2);
  return __gcd(f[x][k], f[y - (1 << k) + 1][k]);
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
    f[i][0] = h[i];
  }
  
  // 预处理 ST 表
  int t = log(n) / log(2) + 1;
  for (int k = 1; k <= t; k++) {
    for (int i = 1; i <= n - (1 << k) + 1; i++) {
      f[i][k] = __gcd(f[i][k - 1], f[i + (1 << k - 1)][k - 1]);
    }
  }

  for (int i = 1; i <= n; i++) {
    int a = 1, b = i;
    while (a < b) {
      int mid = a + b >> 1;
      if (query(mid, i) < h[i]) a = mid + 1;
      else b = mid;
    }
    int l = a;
    a = i, b = n;
    while (a < b) {
      int mid = a + b + 1 >> 1;
      if (query(i, mid) < h[i]) b = mid - 1;
      else a = mid;
    }
    int r = b;
    cout << r - l + 1 << ' ';
  }
}