1 条题解

  • 0
    @ 2026-11-15 15:58:01

    题目分析

    由于 b≥2b \geq 2,因此 aa 的范围就是 [1,N][1, \sqrt{N}],即 a∈[1,109]a \in [1, 10^9]。直接枚举 a,ba, b 的话,时间复杂度是 O(Nlog⁡N)O(\sqrt N \log \sqrt N)。

    20pts

    对于N≤1012N \le 10^{12}的数据,我们可以直接枚举 a,ba, b,时间复杂度是 O(106log⁡106)O(10^6 \log 10^6)。

    100pts

    注意到当 b≥3b \geq 3 时,a∈[1,106]a \in [1, 10^6],因此我们先枚举 a∈[1,106]a \in [1, 10^6],把 a≤106a \leq 10^6,b≥2b \geq 2 的 xx 全部找出来。这里的时间复杂度为 O(106log⁡106)O(10^6 \log 10^6),我们可以将所有的 xx 存储在一个 vector 中,然后对该 vector 进行排序并去重,得到这部分 xx 的数量。

    接下来考虑剩下的 106<a≤10910^6 < a \leq 10^9 且 b=2b = 2 的 xx 的数量。

    一个比较直观的想法是认为这部分的数量为 ⌊N⌋−106\lfloor \sqrt{N} \rfloor - 10^6。但容易发现会有重复计算的情况:如果 a=c2a = c^2,其中 c≤106c \leq 10^6,那么 a2=c4a^2 = c^4,这个数实际上已经在上面计算的 a≤106,b≥2a \leq 10^6, b \geq 2 的部分中出现过。

    因此,我们需要去掉重复的部分。考虑怎样的 aa 是重复的,即存在 b≥2b \geq 2,且 a=cba = c^b(其中 c≤106c \leq 10^6),容易发现这些重复的 aa 都在我们之前枚举计算的范围内,即这些数已经出现在 vector 中。

    因此,我们可以计算 ⌊N⌋−106\lfloor \sqrt{N} \rfloor - 10^6,再减去在 vector 中出现过的 (106,⌊N⌋](10^6, \lfloor \sqrt{N} \rfloor] 的数。通过二分查找找到对应的下标相减即可得到重复的数量。

    • 1

    信息

    ID
    119
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者