GCD of Contiguous Subsequence

$2$整数におけるGCDは，結合律を満たします．また，多くの言語でGCDの単位元は $0$ とされており，整数集合におけるGCDはモノイドであると言えます．従って，セグメント木を用いて，指定区間のGCDは，$\mathrm{O}(\log (N) \log (A))$ で高速に計算可能です．

また，$G(l, r) = \gcd(A_l, A_{l+1}, A_{l+2}, \dots A_{r})$ とすると，$l$ を固定したとき，$G(l, r)$ は $r$ について明らかに広義単調減少です．
従って，数列$A$の区間における左端 $l$ を固定したとき，$G(l, r) \geq M$ を満たす最大の $r$ を $r_1$，$G(l, r) \gt M$ を満たす最大の $r$ を $r_2$ として，$r_1-r_2$ 個が $G(l, r) = M$ を満たします．
よって，$1$ 以上 $N$ 以下の $l$ について上の値を二分探索とセグメント木を用いて $\mathrm{O}(\log^2 (N) \times \log (A))$ で求めることができるため，全体の計算量は $\mathrm{O}(N \times \log^2 (N) \log (A))$ となりますが，セグメント木上で直接二分探索を行うことで，さらに計算量を $\mathrm{O}(N \times \log (N) \log (A))$ に落とすことができます．

コード例（C++）

xxxxxxxxxx

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;

using namespace atcoder;

#define i64 int64_t

​

i64 e() { return 0; }

int main() {

  i64 n, m;

  cin >> n >> m;

  vector<i64> a(n);

  for (i64 &e: a) cin >> e;

  segtree<i64, gcd, e> st(a);

  auto f1 = [=](i64 x) {

    if (x == 0) return true;

    return x >= m;

  };

  auto f2 = [=](i64 x) {

    if (x == 0) return true;

    return x > m;

  };

  i64 ans = 0;

  for(int i=0;i<n;i++) ans += st.max_right(i, f1) - st.max_right(i, f2);

  cout << ans << endl;

}