自动搬运

查看原文

来自洛谷，原作者为

	zgy_123 今天，是你我人生中最年轻的一天。

搬运于2025-08-24 22:45:30，当前版本为作者最后更新于2023-03-11 16:02:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

鸣谢

机房大佬的题解

首先，显而易见，当 $k\ge 3$ 时，是可以通过枚举底数的暴力来解决的，附上 $45$ 分代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
map <ll,bool> mp;
ll cnt;
void solve(ll n,ll k){
	for(ll i=2;i*i*i<=n;i++){//枚举底数，只看3次方就够了
		ll t=i*i,m=2;//表示i^m=t
		while(t<=n/i){
			t*=i,m++;
			if(m<k) continue;//次数不够
			if(mp[t]) continue;//已经有了
			mp[t]=1,cnt++;
		}
	}
}
int main(){
	ll n,k;
	cin>>n>>k;
	solve(n,k);
	if(k==1) cout<<n;
	else if(k>=3) cout<<cnt+1;//加1，因为1没有被判断过
	return 0;
}

（说句闲话，如果这样提交会获得link）

接下来处理平方的判断。

我们知道，$n$ 以内的完全平方数一共有 $\sqrt n$ 个，但是其中有些数字已经被标记过了。

如果一个一个去判断，显然不可行。这时候，我们可以在标记时判断是否为完全平方数。

接下来附上最短 AC 代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
map <ll,bool> mp;
ll x,cnt;
void solve(ll n,ll k){
	for(ll i=2;i*i*i<=n;i++){
		ll t=i*i,m=2;
		while(t<=n/i){
			t*=i,m++;
			if(m<k) continue;
			if(mp[t]) continue;
			if((ll)sqrtl(t)*sqrtl(t)==t) x++;//是完全平方数
			mp[t]=1,cnt++;
		}
	}
}
int main(){
	ll n,k;
	cin>>n>>k;
	solve(n,k);
	if(k==1) cout<<n;
	else if(k>=3) cout<<cnt+1;
	else cout<<(ll)sqrtl(n)+cnt-x;//不用加一，因为在sqrtl里算上了
	return 0;
}

加一些压行后21行

良心提供 $2$ 组 hack 数据：

imput:576460752303423488 2
output:760085356

imput:99 100
output:1

再说句闲话，数据里好像只有 $1\le k \le 3$ 的数据点。

• 2023.3.11 过审
• 2023.3.12 添加压行部分，修改语病
• 2023.3.22 添加 hack 数据