春季测试 2023 幂次

**F出原题

\(3\le k\) 时，\(a\le 10^6\) 可以暴力统计答案，对于重复的贡献可以用类似筛法的东西去维护，因为每个数只会被筛一次，所以是 \(O(n)\) 的，但是统计答案要带一个常数。

\(2 \le k\) 时，对于 \(a\le 10^6\) 的部分用上文的方法筛去即可，对于 \(10^6 < a \le 10^9\) ，\(k\) 只能为 \(2\) ,所以用 \(a\le 10^6\) 中未筛去的来求 \(10^6 < a \le 10^9\) 中筛去的个数，简单容斥一下即可。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INT __int128

ll n,k;
bool vis[10000001];

bool chk(ll x){
    INT s=1,ss=x,ends=n;
    for(ll i=1; i<=k; i++){
        s=s*ss;
        if(s>ends)return 0;
    }
    return 1;
}

// <=1e6
ll calc(ll num){
    ll ans=1;
    for(ll i=2; i<=num; i++){
        if(vis[i])continue;
        INT s=1,ss=i,ED=n,ed=num;
        ll cnt=0;
        while(1){
            if(s<=ED&&cnt>=k)ans++;
            cnt++,s=s*ss;
            if(s>ED)break;
            if(s<=ed&&s!=ss)vis[s]=1;
        }
    }
    return ans;
}

// >1e6
ll maxcalc(ll num){
    if(num<=1000000ll||k>2ll)return calc(num);
    ll sum=calc(1000000ll);
    ll cnt=num-1000000ll,ans=0;
    for(ll i=2; i<=1000000ll; i++){
        if(vis[i])continue;
        INT s=1,ss=i,st=1000000,ed=num;
        while(1){
            if(s>st)ans++;
            s=s*ss;
            if(s>ed)break;
        }
    }
    return (cnt-ans)+sum;
}

int main(){
    scanf("%lld%lld",&n,&k);
    if(k==1){cout<<n<<endl;return 0;}
    ll l=1,ans=1,r=1000000000ll;
    while(l<=r){
        ll mid=((l+r)>>1ll);
        if(chk(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<maxcalc(ans)<<endl;
    return 0;
}