2020-2021:teams:intrepidsword:xvi-open-cup-ukraine
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:intrepidsword:xvi-open-cup-ukraine [2020/07/31 15:25] admin 创建 |
2020-2021:teams:intrepidsword:xvi-open-cup-ukraine [2020/07/31 15:47] (当前版本) admin add J |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| ====== Solutions ====== | ====== Solutions ====== | ||
| + | |||
| + | ===== J. Joining Powers ===== | ||
| + | |||
| + | **题目大意**：定义数列 $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}$ 有多少个，而这是一个经典的反演（当然暴力的复杂度都是能过的）。开根的话还是要二分一下，不知道浮点的精度够不够。 | ||
2020-2021/teams/intrepidsword/xvi-open-cup-ukraine.1596180352.txt.gz · 最后更改: 2020/07/31 15:25 由 admin
