[[数论]] [[计数]] [[并查集 ]] [[Hall 定理]]

前情提要

喜报：CSP-S 89分顺利通过初赛！

今天的题目又是思维题。

题解代码都很短。

显得我很蒻薙。

题解

这个题我是真的喜欢。

简单而巧妙。经过一些观察可以发现要倒着来，如果正着的话后面就是，没有效果。

这个函数满足一个像对数函数一样的性质，可以把乘法转换为加法，就能引出下面的思考了。

还能发现前缀 gcd 的一个性质，前面的是后面的倍数。可以发现倒着贪心有正贡献就行，可以画一个前缀乘数的阶梯图来理解（每一个乘数代表其函数值，最后是加起来）。

然后简单用线性筛求一下，质因数求一下就over。

我现在发现有个问题，经常读题不仔细，太浮躁了捏。比如说就没有看到逐步移动，导致我只写了 sp = 1 的情况，后来发现我所想的就是正解的思路。

后来改正解，发现还是有很多细节的。比如说在树上 dfs 时候求时间要注意，最后求答案也要注意取舍，有时候时间相等的情况也是可行的。

这道题做出来啦。我发现我现在相对擅长计数题。这道题也给了我们一个启发，有时候求一个范围内的情况的时候会很复杂，但是如果去求补集就可能会很简单。

这道题有一点难度，现在也只是相对理解。

对于一种度数分配我们可以求出最大匹配的上限，也可以根据 hall 定理求出下限，并且这其中的值都能取到。

因此只要找到一个 S 和对应的 N(S) 使得然后相差最大就行。

只需要最小值和最大值满足和 l，r 的对应关系即可。

然后就可以用背包（dp），这是怎么想到背包的我也不太理解。

大概是因为一个确定的 S 的大小和对应的 N(S) 的大小和的一个确定的大小所对应的情况数有很多种，而且真实的最小值肯定更小，只要这个满足和 r 的关系肯定满足。而我们只需要求最小值，所以这就相当于容量吧，就可以 dp 了。

但是 dp 的时候不能只有这两个值，不然无法确定情况，还需要有：已经讨论过的点数，有度的点数，已用去的边，S 的大小，sum(S) 的大小。这样就可以有转移方程了，最后再转化成只有 S 和 sum(S)，的背包就行。

很巧妙啊！

暴力的话，直接暴力连边情况然后求最大匹配即可。

前路漫漫，未来可期！