CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

====== Contest Info ======

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

[[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010311|XVI Open Cup named after E.V. Pankratiev. GP of Ukraine]]

====== 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}$ 有多少个，而这是一个经典的反演（当然暴力的复杂度都是能过的）。开根的话还是要二分一下，不知道浮点的精度够不够。

CVBB ACM Team

用户工具

站点工具

页面工具