P9118 [春季测试 2023] 幂次

简要题意

给定两个参数 ，问在区间 中有多少正整数 满足 ，其中 。

策略分析

前置芝士：区间 中完全平方数有 个，这个结论用整除分块很容易就可以证出来。

有了这个结论，我们就已经处理完了这个题中 的情况了，我们来分析剩下的情况。

当 时，显然区间内每个数都可以表示为 ，所以答案就是 。

当 时，底数为 的情况就直接跳过，我们发现现在底数最小是 ，而我们单次计算最大的可能次数就是 ，本题中 ，所以单次最多计算次数为 。所以我们直接暴力枚举就可以了。平方不需要枚举直接用我们的结论，我们从 开始枚举即可，枚举到的数标记一下，下次如果标记过则计数器不操作，碰到完全平方数记一下最后把多算的这一次减掉就行。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#define LL unsigned long long
using namespace std;

namespace SHAWN {
    LL n, k, bcnt, ans, tmp, p;
    //tmp表示底数，p表示幂次，ans是答案，bcnt是重复计算的完全平方数
    map<LL, bool> m;
    int work()
    {
        cin >> n >> k;
        LL bk = sqrtl(n);
        // bk是[1,n]中完全平方数的数量
        for (LL i = 2; i * i * i <= n; ++i) {
            // 从三次根号下n开始枚举
            tmp = i * i; p = 2;
            while (tmp <= n/i) {
                tmp *= i; ++p;
                if (m[tmp] || p < k) { continue; }
                LL k = sqrtl(tmp);
                if (k * k == tmp) { ++bcnt; }
                m[tmp] = true; ++ans;
            }
        }
        if (k == 1) { cout << n << '\n'; }
        else if (k == 2) { cout << ans - bcnt + bk << '\n'; }
        else if (k >= 3) { cout << ans + 1 << '\n';}
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}

特别提醒

本题中要注意的是，开根的时候要用 sqrtl() 而不是 sqrt()，因为我们计算的对象和答案都是长长整型，用 sqrt() 可能会出错。