k==2的部分和https://www.luogu.com.cn/article/r71a5nqd 这篇题解一样，但还是超时，求dalao解答

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#define pi acos(1.0)
#define e exp(-1.0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n,k;
/*bool check(ll a,ll x){
    //cout<<a<<endl;
    for(int i=2;i<=pow(a,1.0/x);i++){
        ll p=a,cnt=0;
        while(p%i==0 && p){
            cnt++;
            p/=i;
            //cout<<i<<" "<<p<<" "<<cnt<<endl;
        }
        if(cnt<x) continue;
        if(p==1) return true;
    }
    return false;
}*/
int sqrt(int x){
	int l = 0, r = 1e9;
	while (l <= r){
		int mid = l + r >> 1;
		if (mid * mid <= x) l = mid + 1;
		else r = mid - 1; 
	}
	return l - 1;
}
map<int,int> m;
int ans=1;
int pf[1000010];

void solve(ll n,ll k){
    for(int i=2;pow(i,k)<=n;i++){
        ll p=k+1,cnt=1;
        ll us=pow(i,k);
        if(m.find(us) == m.end()){
            m[us]=1;
            //cout<<pow(i,k)<<" ";
            while(pow(i,p)<=n){
                ll used=pow(i,p);
                p++;
                if(m.find(used) == m.end()) cnt++;
                m[used]=1;
                //cout<<used<<" ";
            }
            ans+=cnt;
            //cout<<endl;
        }
        
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    if(k==1){
        cout<<n<<endl;
        return 0;
    }
    else if(k>=3){
        solve(n,k);
        cout<<ans<<endl;
        return 0;
    }
    if (k == 2){
		ans = sqrt(n);
		for (int i=1; i<=1000; i++) pf[i*i] = 1;
		if (k == 2) k = 3;
		for (int i=2; i; i++){
			if (m.find(i) != m.end() || pf[i]) continue;
			int now = 1, flag = 0;
			for (int j=1; j<=k; j++){
				if (now > n / i){
					flag = 1;
					break;
				}
				now *= i;
			}
			if (flag) break;
			for (int j=k; j; j++){
				if (m.find(now) == m.end() && j % 2 == 1) ans ++;
				m[now] = 1;
				if (now > n / i) break;
				now *= i;
			}
		}
        cout<<ans<<endl;
	}

    return 0;
}