题目描述
小 Ω 在小学数学课上学到了“幂次”的概念：\(\forall a, b \in \N^+\)，定义 \(a^b\) 为 \(b\) 个 \(a\) 相乘。
她很好奇有多少正整数可以被表示为上述 \(a^b\) 的形式？由于所有正整数 \(m \in N^+\) 总是可以被表示为 \(m^1\) 的形式，因此她要求上述的表示中，必须有 \(b \geq k\)，其中 \(k\) 是她事先选取好的一个正整数。
因此她想知道在 \(1\) 到 \(n\) 中，有多少正整数 \(x\) 可以被表示为 \(x = a^b\) 的形式，其中 \(a, b\) 都是正整数，且 \(b \geq k\)？
输入格式
第一行包含两个正整数 \(n, k\)，意义如上所述。
输出格式
输出一行包含一个非负整数表示对应的答案。
样例 #1
样例输入 #1
99 1
样例输出 #1
99
样例 #2
样例输入 #2
99 3
样例输出 #2
7
样例 #3
样例输入 #3
99 2
样例输出 #3
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\)
【样例 4】
见选手目录下的 power/power4.in 与 power/power4.ans。
【样例 5】
见选手目录下的 power/power5.in 与 power/power5.ans。
【样例 6】
见选手目录下的 power/power6.in 与 power/power6.ans。
【数据范围】
对于所有数据，保证 \(1 \leq n \leq 10^{18}\)，\(1 \leq k \leq 100\)。
| 测试点编号 | \(n \le\) | \(k\) |
|---|---|---|
| 1 | \(10^2\) | \(=1\) |
| 2 | \(10^2\) | \(\ge 2\) |
| 3 | \(10^4\) | \(\ge 3\) |
| 4 | \(10^4\) | \(\ge 2\) |
| 5 | \(10^6\) | \(\ge 3\) |
| 6 | \(10^6\) | \(\ge 2\) |
| 7 | \(10^8\) | \(\ge 3\) |
| 8 | \(10^8\) | \(\ge 2\) |
| 9 | \(10^{10}\) | \(\ge 3\) |
| 10 | \(10^{10}\) | \(\ge 2\) |
| 11 | \(10^{12}\) | \(\ge 3\) |
| 12 | \(10^{12}\) | \(\ge 2\) |
| 13 | \(10^{14}\) | \(\ge 3\) |
| 14 | \(10^{14}\) | \(\ge 2\) |
| 15 | \(10^{16}\) | \(\ge 3\) |
| 16 | \(10^{16}\) | \(\ge 2\) |
| 17 | \(10^{18}\) | \(\ge 3\) |
| 18 | \(10^{18}\) | \(\ge 2\) |
| 19 | \(10^{18}\) | \(\ge 2\) |
| 20 | \(10^{18}\) | \(\ge 2\) |
题解
首先看到这种\(a^b\)这种情况，我就知道能枚举的数量有限，我算了一下，\(x^3=1e18\)时，x的值为251188，所以我先尝试写了一个暴力，那就是枚举指数，枚举底数，用快速幂算一下\(a^b\)的值，同时我用标记数组记录x是否被计算过，这样的时间复杂度也不会很大
上述算法有个问题需要注意，标记数组能算的非常有限，所以只能得到40分的好成绩，所以我需要改进每个数被记录的方式。我用标记数组其实有点儿浪费，因为里面有很多数都没有被用过，比如说2，3，5，6，7等数，所以我想到我用map来记录，修改之后，成绩就变成了75了，好，非常棒
那么剩下的没得分的原因是什么呢？因为刚才的考虑是指数至少是3，如果是2的话，如果n=1e18，那么至少需要枚举到1e9，这样的话，肯定会T，但是我要记录1到1e18里有多少个完全平方数啊？个数非常好记录，同时我要知道他被用过，按照刚才的思路，得把它记录在map中，这样的话，时间复杂度就上去了，这就出现了矛盾
转念一想，我其实没有必要记录到map中，如果在指数大于等于3的时候，我们发现一个数符合条件，我们只需要判断一下，他是否是完全平方数即可，这样时间复杂度就降下来了，嗯，非常棒
另一方面，当指数为1时，肯定n以内的所有数都符合要求，所以个数就是n，所以直接输出，单独处理
有了这样的完整思路，我把代码交上去，发现95分，原因在这里，请看下图
点击查看代码
#include<bits/stdc++.h>
using namespace std;
long long n,ans;
int k;
unordered_map<long long,bool>p;
long long ksm(long long x,int y){
long long ans=1;
while(y){
if(y&1) ans=ans*x;
x=x*x;
y=(y>>1);
}
return ans;
}
bool pd(long long x){
long long k=sqrt(x);
if(k*k==x) return true;
else return false;
}
int main(){
scanf("%lld%d",&n,&k);
if(k==1){
printf("%lld",n);
return 0;
}
if(k==2){
long long mx=sqrtl(n);
ans+=mx-1;
}
for(int i=3;;i++){
if(ksm(2,i)>n) break;
long long x=pow(n,1.0/i);
for(long long j=2;j<=x;j++){
long long d=ksm(j,i);
if(d<=n){
if(p[d]==false) {
if(pd(d)==true&&k==2) continue;
p[d]=true;
ans++;
}
}
else break;
}
}
printf("%lld",ans+1);
return 0;
}