#include<bits/stdc++.h>
using namespace std;
#define int __int128
int n,k;
int qpow(int a,int b){
    __int128 ans=1;
    for(int i=1;i<=b;++i){
        if(ans<0||ans>n||ans>=n/a+1)return 1000000000000000001;
        ans=ans*a;
    }
    return ans;
}
int query(int x,int y){//这里是求最大的z使得z^x<=y
    int lt=0,rt=1e9+1;
    while(lt+1<rt){
        int mid=lt+rt>>1;
//         cout<<"Check2: "<<mid<<'\n';
        if(qpow(mid,x)<=y)lt=mid;
        else rt=mid;
    }
    return lt;
}
int sum;
map<int,bool>mp;
void read(int &x){//读int
        x=0;char c=getchar();
        while(c<'0' || c>'9')c=getchar();
        while(c>='0' && c<='9'){
            x=x*10+c-'0';
            c=getchar();
        } 
    }
    void write(int x){//出int
        if(x==0){putchar(48);return;}
        int len=0,dg[130];
        while(x>0){dg[++len]=x%10;x/=10;}
        for(int i=len;i>=1;i--)putchar(dg[i]+48);
        putchar('\n');
    } 
signed main(){
    read(n);read(k);
    if(k==1){
        write(n);
        return 0;
    }
    bool opt=0;
    if(k==2)opt=1,k++;
    int x=query(k,n),ans=1;
//     cout<<"Check: "<<qpow(500000000,3)<<' '<<k<<' '<<x<<'\n';
    for(int i=2;i<=x;++i){
        int val=qpow(i,k-1);
        for(int j=k;;++j){
            if(val>n)break;
            val*=i;
            if(val>n)break;
//            cout<<"Check: "<<val<<'\n';
            if(mp[val])continue;
            if(opt&&j%2==0)sum++;
            ans++;
            mp[val]=1;
        }
    }
    if(opt){
        ans=ans-sum+(long long)sqrt((long long)n)-1;
    }
    write(ans);
    return 0;
}

WA on #16 & 19

VP代码