RT。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define int long long
using namespace std;
int n,k;
vector<int> v;
int power(int x,int y){
	if(y==0) return 1;
	int res=1;
	while(y){
		if(y&1) res*=x;
		x*=x;
		y>>=1;
	}
	return res;
}
void init(bool flag){
	for(int i=3;i<60;i++){
		if(flag&&(!i&1)) continue;
		for(int j=1;j<=pow(1e18,1.0/i);j++){
			int pw=power(j,i);
			int sq=sqrt(pw);
			if(flag&&sq*sq==pw) continue;
			v.push_back(pw);
			cnt++;
		}
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
}
int work(int x){
	int rk=lower_bound(v.begin(),v.end(),x)-v.begin();
	if(rk==v.size()) rk--;
	else if(v[rk]>x) rk--;
	return rk;
}
signed main(){
	cin>>n>>k;
	if(k>=60) cout<<"1\n";
	else if(k==1) cout<<n<<endl;
	else if(k>2){
		init(0);
		cout<<work(n)+1<<endl;
	}
	else{
		init(1);
		int ans=sqrt(n);
		cout<<work(n)+ans+1<<endl;
	}
	return 0;
}

大致思路是和CF955C的最后一篇题解是差不多的