「春季测试 2023」幂次 题解

题目大意

统计在 $1$ 到 $n$ 中，有多少个正整数可以表示为 $a^b$ 的形式，其中 $a, b$ 都是正整数，且 $b \geq k$。同一个数的不同表示只计数一次。

解题思路

核心算法：枚举底数 + 哈希去重

该解法通过枚举底数 $x$，生成所有满足条件的幂次数，并使用哈希表进行去重。

关键数据结构

unordered_map <ll, bool> mp;  // 用于记录已经出现过的幂次数

算法流程

1. 特殊情况处理

if (k == 1)
    return cout << n, 0;

• 当 $k = 1$ 时，所有 $1$ 到 $n$ 的数都可以表示为 $m^1$，直接输出 $n$

2. 枚举底数生成幂次数

for (ll x = 1; ~qpow(x, max(k, 3)); ++x) {
    Int num = qpow(x, max(k, 3));
    while (num <= n) {
        if (!mp.count(num)) {
            mp[num] = true, ++ans;
            if (check(num)) ++cnt;
        }
        if (x == 1) brk;
        num *= x;
    }
}

关键点：

• 从 $x = 1$ 开始枚举底数
• 使用 max(k, 3) 作为起始指数，确保 $b \geq k$
• 对于每个底数 $x$，生成所有 $x^b$（$b \geq \max(k, 3)$）

3. 快速幂函数

inline ll qpow(Int base, int power) {
    Int res = 1;
    while (power) {
        if (power & 1) res *= base;
        base *= base, power >>= 1;
        if (res > n) return -1;  // 溢出检测
    }
    return res;
}

• 使用 __int128 防止中间结果溢出
• 当结果超过 $n$ 时返回 $-1$

4. 平方数检查

inline bool check(ll x) {
    ll res = sqrtl(x);
    return (res * res == x);
}

• 用于统计完全平方数的数量
• 在 $k = 2$ 的特殊处理中使用

5. $k = 2$ 的特殊处理

if (k > 2)
    return cout << ans, 0;
ll realans = ans + sqrtl(n) - cnt;
cout << realans;

• 当 $k > 2$ 时，直接输出结果
• 当 $k = 2$ 时，需要额外处理平方数的情况

算法原理

为什么这样设计？

1. 枚举底数而非指数：

   • 从底数 $x$ 出发，生成所有 $x^b$（$b \geq k$）
   • 比枚举指数更高效，因为底数的范围更小

2. 起始指数选择：

   • 使用 max(k, 3) 作为起始指数
   • 确保 $b \geq k$，同时避免重复计数问题

3. 去重机制：

   • 使用哈希表记录已出现的数
   • 同一个数的不同幂次表示只计数一次

$k = 2$ 的特殊处理

当 $k = 2$ 时，需要额外考虑所有平方数：

• sqrtl(n)：$1$ 到 $n$ 中的平方数总数
• cnt：已经在枚举过程中统计过的平方数
• realans = ans + sqrtl(n) - cnt：补全所有平方数

复杂度分析

• 时间复杂度：$O(M \log n)$，其中 $M$ 是满足条件的底数数量
• 空间复杂度：$O(\text{不同幂次数的数量})$

样例验证

样例2：$n=99, k=3$

枚举过程：
x=1: 1^3=1, 1^4=1, ... (只计1次)
x=2: 2^3=8, 2^4=16, 2^5=32, 2^6=64
x=3: 3^3=27, 3^4=81
x=4: 4^3=64 (重复)
x=5: 5^3=125 > 99 (停止)

结果：1,8,16,27,32,64,81 共7个

样例3：$n=99, k=2$

在k=3结果基础上，加上所有平方数：
平方数：1,4,9,16,25,36,49,64,81
其中1,16,64,81已统计，补上4,9,25,36,49
最终：7 + 9 - 4 = 12个

代码亮点

1. 溢出处理：使用 __int128 和提前返回机制
2. 去重优化：哈希表快速判断重复
3. 特殊处理：对 $k=1$ 和 $k=2$ 的情况分别优化
4. 精度控制：使用整数运算避免浮点误差

总结

这个解法通过巧妙的底数枚举和哈希去重，高效解决了幂次计数问题。关键创新点：

1. 枚举策略：从底数出发，避免指数枚举的复杂度
2. 特殊处理：针对不同 $k$ 值采用不同策略
3. 溢出防护：使用大整数类型防止计算溢出

该算法能够处理 $n \leq 10^{18}$ 的大规模数据，是一个高效而实用的解决方案。