P9118 题解

zgy_123

2023-03-11 16:02:32

题解

鸣谢@ivy_uu ，我的老师。

机房大佬的题解

首先，显而易见，当 k\ge 3 时，是可以通过枚举底数的暴力来解决的，附上 45 分代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
map <ll,bool> mp;
ll cnt;
void solve(ll n,ll k){
    for(ll i=2;i*i*i<=n;i++){//枚举底数，只看3次方就够了
        ll t=i*i,m=2;//表示i^m=t
        while(t<=n/i){
            t*=i,m++;
            if(m<k) continue;//次数不够
            if(mp[t]) continue;//已经有了
            mp[t]=1,cnt++;
        }
    }
}
int main(){
    ll n,k;
    cin>>n>>k;
    solve(n,k);
    if(k==1) cout<<n;
    else if(k>=3) cout<<cnt+1;//加1，因为1没有被判断过
    return 0;
}

（说句闲话，如果这样提交会获得link）

接下来处理平方的判断。

我们知道，n 以内的完全平方数一共有 \sqrt n 个，但是其中有些数字已经被标记过了。

如果一个一个去判断，显然不可行。这时候，我们可以在标记时判断是否为完全平方数。

接下来附上最短 AC 代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
map <ll,bool> mp;
ll x,cnt;
void solve(ll n,ll k){
    for(ll i=2;i*i*i<=n;i++){
        ll t=i*i,m=2;
        while(t<=n/i){
            t*=i,m++;
            if(m<k) continue;
            if(mp[t]) continue;
            if((ll)sqrtl(t)*sqrtl(t)==t) x++;//是完全平方数
            mp[t]=1,cnt++;
        }
    }
}
int main(){
    ll n,k;
    cin>>n>>k;
    solve(n,k);
    if(k==1) cout<<n;
    else if(k>=3) cout<<cnt+1;
    else cout<<(ll)sqrtl(n)+cnt-x;//不用加一，因为在sqrtl里算上了
    return 0;
}

加一些压行后21行

良心提供 2 组 hack 数据：

imput:576460752303423488 2
output:760085356

imput:99 100
output:1

再说句闲话，数据里好像只有 1\le k \le 3 的数据点。