很妙啊这题。
我们来分析 \(x\) 能到 \(y\) 的数有什么性质。
既然是不互质，那么可以考虑看这个数的最小质因子是什么。
记 \(f(x)\) 为 \(x\) 的最小质因子。
我们将质因子分为 \(2\) 和其它来考虑。
如果一个数的最小质因子不是 \(2\)，那么这个数一定是一个奇数，而它能到达的最小的数 / 能到达它的最大的数一定是一个偶数。（因为 \(x \pm f(x)\) 一定是偶数）
那么我们按照两个数的最小质因子来考虑这个问题。
如果 \(f(x)=2, f(y) = 2\)，那显然两个数不互质，可以直接到达。
如果 \(f(x)=2, f(y) \ne 2\)，那么 \(y\) 能到达的最小的数是 \(y - f(y)\)，而这个数是一个偶数，一定能到达 \(x\)，所以 \(x\) 能到达 \(y\) 的条件就是 \(x \le y - f(y)\)。
如果 \(f(x)\ne2, f(y) = 2\)，同理 \(x\) 能到达 \(y\) 的条件就是 \(x + f(x) \le y\)。
如果 \(f(x) \ne 2, f(y) \ne 2\)，我们可以猜测条件是 \(x + f(x) \le y - f(y)\)。
充分性：如果满足该条件，那么就可以做到 \(x \to x + f(x) \to y - f(y) \to y\)。
必要性：\(x\) 能到达的最小的点 \(x + f(x)\) 不可能为 \(y\)，反之同理，那么如果 \(x + f(x) > y - f(y)\)，说明 \(x\) 先到达了一个不是 \(y\) 且大于 \(y - f(y)\) 的点再到达了 \(y\)，这与 \(y - f(y)\) 是最近点矛盾。
以上条件可以改写成另一个条件：
设每个 \(x\) 对应着一段区间。
如果 \(x\) 为偶数，那么这段区间为 \([x, x + 1)\)。
如果 \(x\) 为奇数，那么这段区间为 \((x - f(x), x + f(x))\)。
两点不能达到说明两点代表的区间相交。我们要找出互相不能到达的点集，就相当于找最多的线段使得都交于一点。我们可以枚举这个交点，然后计算所有经过这个点的线段的权值和，取最大值即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000006;
int n;
long long a[MAXN], b[MAXN];
int pri[MAXN], pcnt, f[MAXN];
int vis[MAXN];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
b[1] = a[1];
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
pri[++pcnt] = i;
f[i] = i;
}
for (int j = 1; j <= pcnt && i * pri[j] <= n; j++) {
vis[i * pri[j]] = 1;
f[i * pri[j]] = pri[j];
if (i % pri[j] == 0) break;
}
}
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
b[i] += a[i], b[i + 1] -= a[i];
} else {
b[i - f[i] + 1] += a[i], b[i + f[i]] -= a[i];
}
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
b[i] += b[i - 1];
ans = max(ans, b[i]);
}
printf("%lld\n", ans);
return 0;
}