枚举指数 再枚举底数

#include<bits/stdc++.h>
#define ll long long
#define db long double
using namespace std;
ll n,k,ans;
db cmp,P;
map<ll,bool> mp;
ll POW(ll A,ll B){
	ll tem=1;
	while (B){
		if (B&1) tem*=A;
		A*=A;
		B>>=1; 
	}
	return tem;
}
int main(){
	scanf("%lld%lld",&n,&k);
	if (k==1){
		printf("%lld",n);
		return 0;
	}
	for (ll i=k;(1ll<<i)<=n;i++){
		if (i==2) continue;
		for (ll j=2;;j++){
			ll p=POW(j,i-1);
			P=n/j;
			if (p>P) break;
			p*=j;
			cmp=sqrtl(p);
			if (k==2&&(ll)cmp==cmp) continue;
			else if(mp[p]==0){
				ans++;
				mp[p]=1;
			}
		}
	}
	if (k==2) ans+=(ll)sqrtl(n);
	else ans++;
	printf("%lld",ans);
	return 0;
}