Non-coprime DAG

题目链接：ARC136E

题目大意

有一个 n 个点的有向图，i 有连向 j 的边当且仅当 i<j 而且 gcd(i,j)>1。
然后给你每个点的点权，你要选一些点，使得任意两个点之间再原路都没有一个点能到另一个点，要你最大化选的点权和。

思路

考虑如何看两个点之间有没有路径。

考虑用 \(2\) 进行中转，毕竟是最小的质数。
所以对是否被 \(2\) 整除分类讨论：（假设看 \(x\) 是否能到 \(y\)，\(x<y\)）

设 \(f(x)\) 是 \(x\) 的最小质数。
\(2|x,2|y\)：都有 \(2\) 公因子，直接连边。
\(2\nmid x,2|y\)：考虑把 \(x\) 变成二的倍数，那用它最小的质数变，其实就是加上它，所以是 \(x\rightarrow x+f(x)\rightarrow y\)
那条件就是 \(x+f(x)\leqslant y\)
\(2|x,2\nmid y\)：相同的想法，先变到 \(y\) 小一点的二倍数，再变到 \(y\)，\(x\rightarrow y-f(y)\rightarrow y\)
那条件就是 \(x\leqslant y-f(y)\)
\(2\nmid x,2\nmid y\)：一个直观的想法是 \(x+f(x)\leqslant y-f(y)\)，考虑证明。

充分性是有的，我们看看必要性，即看看会不会存在不满足这个条件但是连边的情况。
那不满足条件就是 \(y-f(y)\leqslant x+f(x)\)，那从 \(x<y\) 就可以列出：
\(x\leqslant y-f(y)\leqslant x+f(x)\leqslant y\)
（两边的两个小于等于其实是显然的，就从第二第三种情况可以得到）

那 \(x+f(x)\) 一定到不了 \(y\)，所以只能是 \(x\) 直接到 \(y\)，设公共部分是 \(d\)，表示成 \(x=ad,y=bd\)。
而且因为 \(2\nmid x,2\nmid y\)，会有 \(2\nmid a,2\nmid b\)，然后 \(x=ad<(a+1)d<bd=y\)，啊就矛盾了（就算 \(b=a+2\) 也满足上面那个）

所以是对的，那考虑讨论完有什么用。
发现不满足的条件是一个一边闭合一遍开的区间。
但这只是对于它是小的那个或者大的那个。
那如果对于所有的情况，它就是一个闭区间！

观察一下不难看出，对于偶数，就是 \([x,x]\)，对于奇数，就是 \([x-f(x)+1,x+f(x)-1]\)

所以你就是区间求交就代表不能到达。
然后你就区间求交求贡献，差分一下贡献单个加再前缀和加过去就可以。

代码

#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

const int N = 1e6 + 100;
int n, a[N], prime[N], np[N];
ll f[N];

int main() {
	for (int i = 2; i < N; i++) {
		if (!np[i]) np[i] = i, prime[++prime[0]] = i;
		for (int j = 1; j <= prime[0] && i * prime[j] < N; j++) {
			np[i * prime[j]] = prime[j]; if (i % prime[j] == 0) break;
		}
	}
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	f[1] += a[1];
	for (int i = 2; i <= n; i++) {
		if (i & 1) f[i - np[i] + 1] += a[i], f[i + np[i]] -= a[i];
			else f[i] += a[i], f[i + 1] -= a[i];
	}
	
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		f[i] += f[i - 1], ans = max(ans, f[i]);
	printf("%lld", ans);
	
	return 0;
}