思路

有一个显然的暴力做法：对于每个 $a$，标记所有可能的 $a^b$。期望得分 $30$。

考虑“反其道而行之”，求出 $b<k$ 的 $a^b$ 的个数。

对于这个思路，只需求出只能用 $a^1$ 表示的数、只能用 $a^2$ 表示的数......只能用 $a^k$ 表示的数即可。

求出能用 $a^b$ 表示的数并不难，只需写一个二分函数或者调用 pow 函数即可。

关键是要把 $a^{2b}$、$a^{3b}\dots$ 的除去。

除了写个容斥外，还有一个更简单的方法：先把只能用 $a^{2b},a^{3b}\dots$ 表示的数先给求出来即可。

那么最大要求的 $b$ 是多少呢？由于 $2^{70}>10^{18}$，所以随便找一个 $\ge70$ 的数即可。

AC code

#include<bits/stdc++.h>
using namespace std;

long long mi[210];

int check(long long a,long long b,long long p)
{
	long long ans=1;
	for(int i=0;i<b;i++)
	{
		if(p/ans<a)return 1;
		ans*=a;
	}
	if(ans==p)return 0;
	else return -1;
}

long long kf(long long n,long long k)
{
	long long l=1,r=n;
	while(l+1<r)
	{
		long long mid=(l+r+1)/2;
		if(check(mid,k,n)<0)l=mid;
		else r=mid;
	}
	if(check(r,k,n)==0)return r;
	return l;
}

int main()
{
	long long n,k;
	cin>>n>>k;
	for(int i=200;i>0;i--)
	{
		long long tp=kf(n,i)-1;//自写开方函数
		
		for(int j=i;j<=200;j+=i)tp-=mi[j];
		mi[i]=tp;
	}
	long long ans=n-1;
	for(int i=1;i<k;i++)ans-=mi[i];
	cout<<ans+1;
	return 0;
}