i saw ancestor

s4CRIF1CbUbbL3AtIAly · 2023-10-01 11:58:25 · 题解

Problem link

模拟赛有人搬了这道题。

首先可以猜一个结论：对于所有不同的等价类（就是说对于每一个对应的左边的编号集合相同的右边的集合）权值的和（记为 S_x）的 \gcd 即为答案。

这个结论看上去很对，但是感觉好像又可以构造反例。所以我们来证明一下它是对的。

首先这个 \gcd 必然合法（即无论左边怎么取，右边的值都是它的倍数），因为对于任意不同的等价类我们都取了权值的和算入 \gcd。

那为什么这个值是最优的呢？我们先设它为 g。

如果存在一个 w>g 且 w 符合要求，那么必然存在至少一个等价类 k 使得 w\nmid S_k。

那么当选取到 k 的时候必须要存在一个 k'\subset k 且 w\nmid S_{k'} 才能使它们的和是 w 的倍数。

于是以此递归直到找不到 k'，w 就不满足条件了。

因此我们就证明完了。

set 其实可以直接扔到 map 里，不需要哈希。

模拟赛的时候 saw ancestor，100->20