[ARC136E] Non-coprime DAG

显然只和可达性有关。注意到这样一件事情：所有偶数都是可达的。而对于奇数而言，\((x - \operatorname{lpf}(x), x + \operatorname{lpf}(x))\) 这个区间内的数和 \(x\) 一定不可达。定义 \(x\) 控制的区间为 \((x - \operatorname{lpf}(x), x + \operatorname{lpf}(x))\)。由于偶数作为媒介，两奇数可达当且仅当他们控制的区间不交。同时，一个奇数和一个偶数可达当且仅当偶数不在奇数控制的区间内。我们定义偶数控制的区间只包含它本身，这样上面的性质对所有正整数都成立了。现在我们要找到一个若干个数使得他们控制的区间两两相交，直接枚举交点转化成区间加单点求值即可。

int main() {
  read(n);
  Sieve(n);
  for(int i = 1; i <= n; ++i) {
    read(a[i]);
    if(i > 1 && i % 2 == 1) {
      b[i - lpf[i] + 1] += a[i];
      b[min(i + lpf[i] - 1, n + 1)] -= a[i];
    } else if(i > 1) b[i] += a[i], b[i + 1] -= a[i];
  }
  LL ans = b[0] = a[1];
  for(int i = 1; i <= n; ++i) {
    b[i] += b[i - 1];
    if(b[i] > ans) ans = b[i];
  }
  printf("%lld\n",ans);
}