date: 2020-07-30 13:11~18:11

XVI Open Cup named after E.V. Pankratiev. GP of Ukraine

题目大意：定义数列 $s_{ij}=j^{i}$，给你若干个 $s_{i}$，将它们归并起来（合并相同元素），问第 $n$ 个数。保证答案 $\le10^{17}$。

题解：二分后转化为求 $1\sim\text{mid}$ 中有多少个元素。考虑容斥，答案为 $\sum_{S\neq\emptyset}(-1)^{|S|+1}\lfloor\sqrt[\text{lcm}(S)]{\text{mid}}\rfloor$。注意到，只要 $\text{lcm}$ 大于 $60$，就只有 $1$ 满足要求了，而 $1$ 始终在数列中，因而不妨容斥时先不管它。这样我们只需容斥出各个 $\text{lcm}$ 有多少个，而这是一个经典的反演（当然暴力的复杂度都是能过的）。开根的话还是要二分一下，不知道浮点的精度够不够。