安吉D4-B - Jerry's blog

原题呈现

题目描述#

小 Ω 在小学数学课上学到了“幂次”的概念： $\forall a, b \in \mathbb{N}^+$ ，定义 $a^b$ 为 $b$ 个 $a$ 相乘．

她很好奇有多少正整数可以被表示为上述 $a^b$ 的形式？由于所有正整数 $m \in \mathbb{N}^+$ 总是可以被表示为 $m^1$ 的形式，因此她要求上述的表示中，必须有 $b \geq k$ ，其中 $k$ 是她事先选取好的一个正整数．

因此她想知道在 $1$ 到 $n$ 中，有多少正整数 $x$ 可以被表示为 $x = a^b$ 的形式，其中 $a, b$ 都是正整数，且 $b \geq k$ ？

输入格式#

第一行包含两个正整数 $n, k$ ，意义如上所述．

输出格式#

输出一行包含一个非负整数表示对应的答案．

输入输出样例 #1#

输入 #1#

1
99 1

输出 #1#

1
99

输入输出样例 #2#

输入 #2#

1
99 3

输出 #2#

1
7

输入输出样例 #3#

输入 #3#

1
99 2

输出 #3#

1
12

说明/提示#

【样例 2 解释】

以下是全部 $7$ 组符合题意的正整数及对应的一种合法的表示方法．

1 = 1^3, 8 = 2^3, 16 = 2^4, 27 = 3^3, 32 = 2^5, 64 = 4^3, 81 = 3^4

注意某些正整数可能有多种合法的表示方法，例如 $64$ 还可以表示为 $64 = 2^6$ ．

但根据题意，同一个数的不同的合法表示方法只会被计入一次．

【样例 3 解释】

以下是全部 $12$ 组符合题意的正整数及对应的一种合法的表示方法．

1 = 1^2, 4 = 2^2, 8 = 2^3, 9 = 3^2, 16 = 4^2, 25 = 5^2, 27 = 3^3, 32 = 2^5, 36 = 6^2, 49 = 7^2, 64 = 8^2, 81 = 9^2

【数据范围】

对于所有数据，保证 $1 \leq n \leq 10^{18}$ ， $1 \leq k \leq 100$ ．

测试点编号	$n \le$	$k$
1	$10^2$	$=1$
2	^	$\ge2$
3	$10^4$	$\ge3$
4	^	$\ge2$
5	$10^6$	$\ge3$
6	^	$\ge2$
7	$10^8$	$\ge3$
8	^	$\ge2$
9	$10^{10}$	$\ge3$
10	^	$\ge2$
11	$10^{12}$	$\ge3$
12	^	$\ge2$
13	$10^{14}$	$\ge3$
14	^	$\ge2$
15	$10^{16}$	$\ge3$
16	^	$\ge2$
17	$10^{18}$	$\ge3$
18	^	$\ge2$
19	^	^
20	^	^

不难得知，使用次方的逆运算 $\lfloor\sqrt[k]{n}\rfloor$ 可以快速得知小于 $n$ 的完全 $k$ 次方数的数量．那么答案就是

\sum_{i=k}^{\log_{2}10^{18}} \lfloor\sqrt[i]{n}\rfloor

对于 8 来说，它既是完全平方数，也是完全立方数，在 $i=1$ 、 $i=2$ 和 $i=3$ 时都被算了一次，重复算了两次．为了去除这种重复，我们定义 f[i] 表示满足下列条件的正整数数量：

小于 $n$
是完全 $k$ 次方数
不是完全 $j\times k$ 次方数， $j\in\mathbb{N}, j>1$

因此，f[i] 的数值就等于满足条件 1 和 2 的正整数数量（即 $\lfloor\sqrt[k]{n}\rfloor$ ）减去不满足条件 3 的正整数数量（ $\log_{2}10^{18}\approx 60$ ）：

f[i] = \lfloor\sqrt[k]{n}\rfloor - 1 - \sum_{j=k}^{60}f[i\times j]

上式中的 -1 是因为去除以 1 为底数的数，以 1 为底数，任意自然数为指数都为 1．所以每一次计算 $\lfloor\sqrt[k]{n}\rfloor$ ，1 都会被算 1 遍，在这里减去，最后统一加 1．

最终答案为： $1 + \sum_{i=k}^{60} f[i]$ ．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
ll n, k, f[62], ans;
5
int main() {
6
    cin >> n >> k;
7

8
    for (int i = 60; i >= k; i--) {
9
        f[i] = powl(n, 1.0 / i) - 1;
10
        for (int j = 2; j * i <= 60; j++) {
11
            f[i] -= f[j * i];
12
        }
13
    }
14
    for (int i = k; i <= 60; i++) {
15
        ans += f[i];
16
    }
17
    cout << ans + 1;
18
}

音乐

音乐