Instant Noodles 题解

Pwtking · 2023-10-25 14:34:36 · 题解

传送门

首先，有结论：\gcd(a,b)=\gcd(a,a+b)=\gcd(a,b,a+b)，所以我们可以考虑每个右部点分别的贡献以降低复杂度。

• 为什么不从左部点进行考虑：

• 从左部点考虑的话，一个思路是把每一个左部点作为单独的一个 S，求出所有 f(S) 的 \gcd，但是你发现你样例都过不了，因为有右部点的权值被重复计算了。

• 所以我们考虑把每次做过贡献的右部点打上标记，每一次只选没打标记的进行贡献,但是这样还是错误的：比如一个右部点 a 分别被两个 S_1,S_2 所包含，其中的一个 S_1 只包含一个右部点 a，并且枚举 S_1 的顺序更靠后。此时 a 已经做过贡献被删除，但此时 a 贡献是被包含在 S_2 中的贡献，而其真正的贡献是 \gcd(f(S_1),f(S_2))。

所以我们考虑每一个右部点对答案的贡献。如果一个两个右部点所连接的左部点的点集相同的话，意味着这两个右部点做贡献的时候一定是一起出现，所以我们把这两个右部点合并，其权值这两个右部点的权值和（三个点及以上的时候也同理）。

最后求出所有右部点权值的 \gcd 即可。