WA on #20

#include<algorithm>
#include<cstdio>
#include<map>
#include<math.h>
long long read(){
    long long x=0,f=1;
    char ac=getchar();
    while(ac<'0'||ac>'9'){
        if(ac=='-') f=-1;
        ac=getchar();
    }
    while(ac>='0'&&ac<='9'){
        x=(x<<3)+(x<<1)+(ac-'0');
        ac=getchar();
    }
    return x*f;
}
int read2(){
    int x=0,f=1;
    char ac=getchar();
    while(ac<'0'||ac>'9'){
        if(ac=='-') f=-1;
        ac=getchar();
    }
    while(ac>='0'&&ac<='9'){
        x=(x<<3)+(x<<1)+(ac-'0');
        ac=getchar();
    }
    return x*f;
}
long long n,k,ans1,ans2;
std::map<long long,bool> m;
bool istwo;
long long quick(long long a,int b){
    long long ans=1;
    while(b){
        if(b&1){
            if((n/ans)<a) return -1;
            ans*=a;
        }
        if((n/a)<a) return b==1?ans:-1;
        a*=a;
        b>>=1;
    }
    return ans;
}
int maxn(){
    int l=1,r=1e9,ans;
    while(l<=r){
        int mid=l+r>>1;
        if(quick(mid,k)!=-1){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return ans;
}
int sqrtt(long long x){
    int l=1,r=1e9,ans;
    while(l<=r){
        int mid=l+r>>1;
        if(1ll*mid*mid<n){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    return ans;
}
signed main(){
    n=read(),k=read2();
    if(k==1){
        printf("%lld",n);
        return 0;
    }
    if(k>=60){
        printf("1");
        return 0;
    }
    if(k==2){
        istwo=1;
        k++;
    }
    int cnt=maxn();
    for(int i=2;i<=cnt;i++){
        long long now=quick(1ll*i,k-1);
        for(int j=k;;j++){
            if(n/now<i) break;
            now*=i;
            if(m[now]) continue;
            if(j%2==0) ans2++;
            ans1++;
            m[now]=1;
        }
    }
    if(istwo){
        printf("%lld",ans1-ans2+sqrtt(n));
    }
    else printf("%lld",ans1+1);
    return 0;
}