.POI XIV Stage.1 Queries Zap 解题报告.pdfVIP

POI XIV Stage.1 《Queries》解题报告 Kwc-Oliver 《Queries》解题报告 —POI XIV Stage.1 ZAP By Kwc-Oliver 【问题简述】 有 个询问，每次询问 ，问有多少个 满足 ， 且 。 【引言】 BZOJ 2045是本题的简化版。唯一的不同就是本题有很多组询问。当问题量化之后 如何处理、如何去除冗余，将是本文所要讨论的。最后利用此方法解决拓展问题—NOI 2010 day1 《能量采集》一题。 【分析】 1 先将问题转化为:对于给定的 ，求有多少组 满足 ，且 。 那么下文的 分别为原题中的 。 设 表示有多少组 ，且 互质。 设 表示有多少组 ，且 。 那么显然有： 根据容斥原理有： 其中 1本文所有””均表示整除 第1 页 POI XIV Stage.1 《Queries》解题报告 Kwc-Oliver                这个可以自己画个图，根据容斥原理是可以得到的，下面附上一个简图。 注意到 与 无关。所以可以预处理出来。 那么现在，对于每个询问我们可以做到。但由于有50000组，所以还需优化。 由于预处理不影响时间复杂度，所以我们仍然考虑 ∑ 对于其中连续的项，有可能有 。那么对于 这项，我们可以直接算出，即为 那么将这些冗余去除后，时间复杂度是否有改善呢？ 对于，其不同的取值最多只有，对于也一样。 但是二元组 的取值却不是 。 第2 页 POI XIV Stage.1 《Queries》解题报告 Kwc-Oliver 如图所示，可以发现这是一个用 点来划分区间的模型，所以二元组最多 只有 个。 所以这道题，我们可以在 √ √ 的时间内完成。 最后说一点关于实现的问题： 1，预处理 时要注意大于 的质数，此时应处理好其为有一个质因子的情况。 2，如何求得二元组 取值范围相同的一段：对于当前点，其向右延伸最远 为 。其原理为为下界，那么就是上界了。 【拓展