目录
写在前面
我是飞物。
CF1981D
2400
妈的好诡异的题场上拿到这题我都不知道我要干啥呃呃
考虑到每个合数均为若干质数的乘积，则若构造方案中有合数，可以将合数替换为质数从而减少使用的权值的种类数，于是仅需考虑使用质数构造，则此时并不需要考虑具体使用了哪些质数，且此时 \(a_{i}\times a_{i + 1} = a_{j}\times a_{j + 1}\) 的充要条件即为无序对 \((a_{i}, a_{i + 1}) = (a_{j}, a_{j + 1})\)。该限制和无重边很像。则若已知需要 \(m\) 种质数进行构造，问题等价于在一张 \(m\) 个点的带自环的完全图中，找到一条边数为 \(n - 1\) 的欧拉路径。使用 Hierholzer 算法即可 \(O(m^2)\) 地解决。
于是考虑至少需要多少种质数才可构造出 \(n-1\) 条边的欧拉路径。由于自环的贡献显然可以全部得到，于是仅需考虑非自环边的影响。若 \(m\) 为奇数则所有点度数均为偶数，显然最长欧拉路径可以包括所有非自环边，数量为 \(\frac{m(m - 1)}{2}\)；若 \(m\) 为偶数则所有点度数均为奇数，则需要屏蔽一些边使得该图存在欧拉路径，使非零度点是连通的，且有不多于 2 个奇度点。发现删去一条边至多使奇度数点减 2，则至少需要删除 \(\frac{m}{2} - 1\) 条边，且使这些边无交点。则钦定删除 \((2, 3), (4, 5), \cdots, (m - 2), (m - 1)\) 即可，则最长欧拉路径包括的非自环边数为 \(\frac{m(m - 1)}{2} - \frac{m}{2} + 1\)。
发现上面的式子关于 \(m\) 是单调的，则可以二分求得至少需要多少种质数。发现 \(n=10^6\) 时 \(m\approx 1100\)，显然不会超过上界 \(3\times 10^5\)。
另外先尝试了不显式地建图然而比用 vector 显式建图怎么慢十倍啊我草
CF1992F
写在最后
我是……？
标签：frac,质数,路径,合数,times,2024,杂题,集训,欧拉 From： https://www.cnblogs.com/luckyblock/p/18309076