LG-P9118 [春季测试 2023] 幂次 Solution

更好的阅读体验戳此进入

游记戳此进入

题面

给定 $n$$n$，$k$$k$，求在 $[1,n]$$[1, n]$ 中有多少数可以表示为 $a^b$$a^b$，其中 $b\ge k$$b \ge k$。

Solution

感觉差不多是绿题的难度，不卡精度的话应该算黄题难度，赛时的阴间思路在游记里了，这里说一下正解。

不难发现对于任意的合法的 $b$$b$，一定满足 $a\le {}^k\sqrt{n}$$a \le {^k\sqrt{n}}$，则对于 $k\ge 3$$k \ge 3$ 的情况，$a$$a$ 最大也是在 ${10}^6$$10^6$ 的范围，那么我们直接枚举所有的 $a$$a$，并枚举其所有合法的 $a^b$$a^b$，然后将其全部丢到 unordered_set 里，最后直接输出其 size() 即可，考虑这样的复杂度，显然枚举 $a$$a$ 是 $O(n^{\frac{1}{k}})$$O(n^{\frac{1}{k}})$ 的，枚举幂次是 $O(\log n)$$O(\log n)$ 的，则复杂度 $O(n^{\frac{1}{k}}\log n)$$O(n^{\frac{1}{k}} \log n)$，对于 $k\ge 3$$k \ge 3$ 的情况是随便过的。

考虑对于 $k=2$$k = 2$ 的情况，不难发现这东西也是很显然的，枚举一下 unordered_set 中的所有数，若其为完全平方数的话贡献 $-1$$-1$，然后最后在答案中加上 $\lfloor \sqrt{n}\rfloor$$\lfloor \sqrt{n} \rfloor$ 即可。不难发现此时复杂度为 $O(n^{\frac{1}{3}}\log n)$$O(n^{\frac{1}{3}} \log n)$，可以通过。

同时不难发现对于 $\sqrt{n}$$\sqrt{n}$，这个东西如果直接朴素的用 double 的 sqrt() 函数的话会丢失精度，所以此时需考虑使用二分或 long double 或 __float128，前者会多一个 $\log$$\log$，对于上述 $k=2$$k = 2$ 的理论复杂度也是正确的。而用 __float128 会多一个十分巨大的甚至高于 $\log$$\log$ 的常数，不建议使用。当然我们也可以朴素地使用 sqrt() 然后取其返回值一段较小的邻域进行验证，一般 $\pm 1$$\pm 1$ 就够用了。

Code

xxxxxxxxxx
72
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
ll N, K;
27
unordered_set < ll > legal;
28
ll ans(0);
29

30
int main(){
31
    auto qpow_with_lim = [](ll a, ll b)->ll{
32
        ll ret(1), mul(a);
33
        while(b){
34
            if(b & 1)
35
                ret = (__int128_t)ret * mul > N ? N + 1 : ret * mul;
36
            b >>= 1;
37
            mul = (__int128_t)mul * mul > N ? N + 1 : mul * mul;
38
        }return ret;
39
    };
40

41
    N = read < ll >(), K = read();
42
    if(K == 1)printf("%lld\n", N), exit(0);
43
    legal.insert(1);
44
    for(ll i = 2; i <= (ll)1e6; ++i){
45
        auto cur = (__int128_t)qpow_with_lim(i, K == 2 ? 3 : K);
46
        while(cur <= N)
47
            legal.insert(cur), cur *= i;
48
    }ans += legal.size();
49
    if(K == 2){
50
        for(auto v : legal)
51
            if((ll)sqrt((ld)v) * (ll)sqrt((ld)v) == v)--ans;
52
        ans += (ll)floor(sqrt((ld)N));
53
    }printf("%lld\n", ans);
54
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
55
    return 0;
56
}
57

58
template < typename T >
59
inline T read(void){
60
    T ret(0);
61
    int flag(1);
62
    char c = getchar();
63
    while(c != '-' && !isdigit(c))c = getchar();
64
    if(c == '-')flag = -1, c = getchar();
65
    while(isdigit(c)){
66
        ret *= 10;
67
        ret += int(c - '0');
68
        c = getchar();
69
    }
70
    ret *= flag;
71
    return ret;
72
}

UPD

update-2023_03_06 初稿