[春季测试 2023] 幂次
题目描述
小 Ω 在小学数学课上学到了“幂次”的概念：\(\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\) |
题解：
算法复杂度：i*i<=\(10^{18}\), 枚举i是\(10^9\)，可以枚举一下所有\(x^p\)的，85分。
#include<bits/stdc++.h>
using namespace std ;
long long n , k , ans=1 ;
bool vis[1000000005] ;
int main(){
freopen("power.in" , "r" , stdin) ;
freopen("power.out" , "w" , stdout) ;
scanf("%lld%lld" , &n , &k) ;
if(k==1){
cout << n ;
return 0 ;
}
for(int i=2 ; i*i<=n ; i++){
if(vis[i]==1) continue ;
bool flag = false ;
int b=1 ;
long long x = i ;
while(n/x >= i){
b++ ;
x *= i ;
if(x<=1000000000) vis[x] = 1 ;
if(b>=k){
ans++ ;
flag = true ;
}
}
if(flag==false) break ;
}
cout << ans ;
return 0 ;
}
上述为yxm的代码。
进行优化：\(i*i*i<=10^{18}, 枚举i是10^6\)，可以枚举一下所有\(x^p\)的，100分。
算一下所有p>=3的情况，去除p==2的情况，可以判断一下里面是完全平方数的数字。加上正好等于sqrt(l)
当k>3的时候，可以用下面的方法实现:
s*=i; K++;
if(mp[s]) continue; mp[s] = 1;
if(K >= k) cnt++;
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
map<ll, bool> mp;
ll zt, tot, cnt,k,r;
void init(ll n){
for(ll i=2;i*i*i<=n;i++){//1e6
ll s=i*i; ll K = 2;
while(s<=n/i){
s*=i; K++;
if(mp[s]) continue; mp[s] = 1;
if(K >= k) cnt++;
ll sq = sqrtl(s);
if(sq * sq == s && sq <= (ll)sqrtl(n)) zt++;
tot++;
}
}
}
int main(){
cin>>r>>k;
init(r);
if(k == 1) cout<<r<<endl;
else if(k == 3) cout<<tot+1<<endl;
else if(k == 2) cout<<(ll)sqrtl(r)+tot-zt<<endl;
else cout<<cnt+1<<endl;
return 0;
}