先讲最暴力的做法：
时显然。
时可以算出，所以显然可以枚举。
那么时怎么算呢，直接在枚举大于等于三时的情况时统计一下完全平方数的个数这里直接开平方减就行了。
显然愚笨的我并未在做题时想出如此高明的办法。我第一反应是这样的。我们暂且规定顺便规定一下将一个数表示成的形式且,均为整数且取最大能取的数时的形式称为最大指数形式，称为该数的最大指数。然后定义函数表示最大指数为的数的个数，然后表示为指数能是的数的个数，显然。
这里我们先排除1(因为1可以表示成1的任意次方不好搞)，然后我就想然后我们就能发现括号内的系数其实和是有关系的（很容易想明白），然后再处理一下1的问题就可以写出的函数了，而且除去1，最大的指数是。那么再回到问题上我们该怎么求呢？我们从1枚举到k，然后去算最大指数为这个数的数的个数。那么怎么算个数呢？我们稍微写一下就能发现，写成最大指数形式时底数的最大指数是1，这不就到f上来了吗？那么最大指数为的个数就是，然后我们就可以写出代码了。
总时间复杂度是。
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
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, k;
int mu[61], pri[61], cnt;
bool vis[61];
ll ans;
void init() {
mu[1] = 1;
for (int i = 2; i < 61; ++i) {
if(!vis[i]) {
pri[cnt++] = i;
mu[i] = -1;
}
for (int j = 0; j < cnt && i * pri[j] < 61; ++j) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) {
mu[i * pri[j]] = 0;
break;
}
mu[i * pri[j]] = -mu[i];
}
}
}
ll f(ll n) {
ll ans = 0;
double tmp = log2(n);
for (int i = 2; i <= tmp; ++i) {
ans -= mu[i] * (floor(pow<long double>(n, 1.0 / i)) - 1);
}
return n - ans - 1;
}
int main() {
scanf("%lld%lld", &n, &k);
init();
if (k == 1) {
printf("%lld", n);
return 0;
}
ans = n;
for (int i = 1; i < k; ++i) {
ans -= f(floor(pow<long double>(n, 1.0 / i)));
}
printf("%lld", ans);
return 0;
}
|
