题面 标题比题面好懂系列. 题目就是要求所有环中边权之和与环长之比的最小值. 令点权为1(方便统计长度. 更一般的0/1分数规划题中点权是可以任意取的, 后续推导一致), 则 $ ans=\sum{e.w}/\sum{v.w}$ $ \sum{e.w}-ans*\sum{v.w}=0$ $ \sum(e.w-ans*v.w)=0$ $ \sum_{…
以下是一些基础性数论结论的简单复习, 和一些代码实现. 证明的坑慢慢补. 内容极其简单基础, 巨佬勿喷... 约数 算术基本定理的推论 设$ N=\prod_{i=1}^{m}P_i^{c_i}$(唯一分解), 则 n的正约数共$$\prod_{i=1}^{m}(c_i+1)$$个. n的所有正约数之和为$$\prod_{i=1}^{m}(\sum…