*P3532 [POI2012]ODL-Distance

POI 合集。

考虑在 $i$ 和 $p\times i\ (p\in \mathbb{P})$ 之间连边，题目相当于在这张图上撒 $n$ 个关键点，求距离每个关键点最近且非本身的关键点的最小编号。对每个点记录距离该点最近和第二近的关键点距离与编号，一遍 BFS 即可，但是常数太大，不开 O2 难以通过。

设 $\omega(i)$ 表示 $i$ 的质因子个数，则 $\mathrm{dis}(i,j)=\omega(i)+\omega(j)-2\omega(\gcd(i,j))$。考虑枚举 $d=\gcd(i,j)$，那么减号后面的部分就确定了，对于一个固定的 $i$，我们显然要让 $(\omega(j),buc_j)$ 这一二元组最小，其中 $buc_j$ 表示 $a$ 值为 $j$ 的最小位置。

考虑枚举 $d$ 的倍数 $kd$，求出 $\min_{k\geq 1,kd\leq r}(\omega(kd),buc_{kd})$，设为 $(x,y)$ 以及取到最小值的位置为 $td$。 那么对于所有 $k\neq t$，我们用 $td$ 和 $kd$ 互相更新。$kd$ 就相当于上面的 $i$，而 $td$ 充当了使得 $(\omega(j),buc_j)$ 最小的 $j$。

每个 $\gcd$ 都会被枚举到，因此算法正确。时间复杂度是调和级数的线性对数。由于小常数，成功拿到了最优解（2021.12.19）。

const int N = 1e6 + 5;
int n, mx, a[N], buc[N], ans[N], fc[N]; pii dis[N];
int cnt, vis[N], pr[N], mpr[N], chk[N];
void sieve() {
	dis[1] = {N, 0};
	for(int i = 2; i <= mx; i++) {
		dis[i] = {N, 0};
		if(!vis[i]) pr[++cnt] = i, mpr[i] = i;
		for(int j = 1; j <= cnt && i * pr[j] <= mx; j++) {
			vis[i * pr[j]] = 1, mpr[i * pr[j]] = pr[j];
			if(i % pr[j] == 0) break;
		} chk[i] = chk[i / mpr[i]] + 1;
	}
} 
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		a[i] = read(), cmax(mx, a[i]);
		if(buc[a[i]]) {
			ans[i] = buc[a[i]];
			if(!ans[buc[a[i]]]) ans[buc[a[i]]] = i;
		} else buc[a[i]] = i;
	} sieve();
	for(int i = 1; i <= mx; i++) {
		pii best = {N, 0};
		for(int j = i, dv = 1; j <= mx; j += i, dv++)
			if(buc[j]) cmin(best, (pii){chk[dv], buc[j]});
		for(int j = i, dv = 1; j <= mx; j += i, dv++) if(buc[j] != best.se && buc[j])
			cmin(dis[j], (pii){best.fi + chk[dv], best.se}),
			cmin(dis[a[best.se]], (pii){best.fi + chk[dv], buc[j]});
		if(buc[i] && !ans[buc[i]]) ans[buc[i]] = dis[i].se;
	} for(int i = 1; i <= n; i++) print(ans[i]), pc('\n');
	return flush(), 0;
}