ARC136E

首先显然节点 \(1\) 必选，下面就忽略节点 \(1\) 了。

之后先考虑可达性，定义 \(f(n)\) 为 \(n\) 的最小质因数。

那么 \(x\) 能到 \(y\) 当且仅当满足以下四种条件之一：

• \(x\equiv0\pmod2\) 且 \(y\equiv0\pmod2\)
• \(x\equiv1\pmod2\) 且 \(y\equiv0\pmod2\)，并且 \(x+f(x)\le y\)
• \(x\equiv0\pmod2\) 且 \(y\equiv1\pmod2\)，并且 \(x\le y-f(y)\)
• \(x\equiv0\pmod1\) 且 \(y\equiv0\pmod1\)，并且 \(x+f(x)\le y-f(y)\)

第一种情况显然。

对于节点 \(x\) 它能走到的最小可达点是 \(x+f(x)\)，如果 \(x\) 是奇数，那么 \(x+f(x)\) 是偶数，所以只要 \(x+f(x)\le y\) 就能走到，这就是第二种情况。

同理 \(y-f(y)\) 是能走到 \(y\) 的最大可达点，对应第三种情况。

最后一种情况的充分性显然，下面证明必要性:

假设 \(y-f(y)\lt x+f(x)\)，但是 \(x\) 依旧能走到 \(y\)。那么由上面的分析得 \(x\) 要是能走到 \(y\) 肯定是直达的。因此设 \(x=ac,y=bc\)，\(a,b,c\) 都是奇数，且 \(a\lt b,c\gt1\)。

那么 \(c\) 显然是不小于 \(f(x)\) 和 \(f(y)\) 的，那么有 \(x+f(x)\le x+c\)，\(y-c\le y-f(y)\)，因为 \(a\lt b\) 且 \(a,b\) 均是奇数，所以 \(b-a\ge2\)，所以 \(x+c\le y-c\)，所以 \(x+f(x)\le y-f(y)\)，与假设矛盾。证毕。

由上面的分析可以想到构造区间

• \(x\equiv0\pmod2\)：\(l(x)=r(x)=x\)
• \(x\equiv1\pmod2\)：\(l(x)=x-f(x)+1,r(x)=x+f(x)-1\)。

那么 \(x\) 走不到 \(y\) 就说明 \([l(x),r(x)]\cap [l(y),r(y)]\ne\emptyset\)，那么差分一下，枚举交集是哪个点即可。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000000;
int n;
int a[N+5]; ll sum[N+5];
bool vis[N+5];
int pri[N], tot;
int mn[N+5];

void init() {
	for (int i = 2; i <= N; ++i) {
		if (!vis[i]) pri[++tot] = i, mn[i] = i;
		for (int j = 1; j <= tot && i * pri[j] <= N; ++j) {
			vis[i * pri[j]] = 1;
			mn[i * pri[j]] = pri[j];
			if (i % pri[j] == 0) break;
		}
	}
}

int main() {
	init();
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = 1; i <= n; ++i) {
		int l, r;
		if (i == 1) l = 1, r = n;
		else if (i % 2 == 0) l = r = i;
		else l = i - mn[i] + 1, r = i + mn[i] - 1;
		sum[max(1, l)] += a[i], sum[min(n + 1, r + 1)] -= a[i];
	}
	for (int i = 1; i <= n; ++i) sum[i] += sum[i - 1];
	ll ans = 0;
	for (int i = 1; i <= n; ++i) ans = max(ans, sum[i]);
	printf("%lld", ans);
	return 0;
}

原文地址：http://www.cnblogs.com/Kobe303/p/16818768.html