70tps求调
查看原帖
70tps求调
657623
zse159aw48xd26楼主2023/3/29 17:03

不知道为何出错了 错误提示: Runtime Error. Received signal 6: Aborted / IOT trap. 提交记录

#include<bits/stdc++.h>
#include<bitset>
#define ll long long
using namespace std;
const int N=1e9;
bitset<N+5> vis;
ll n,ans=1,k,tot;
inline long long read(){
	long long x=0,y=1;char ch=getchar();
	while(ch<'0'||ch>'9'){	if(ch=='-')	y=-1;	ch=getchar();	}
	while(ch>='0'&&ch<='9'){	x=x*10+ch-'0';	ch=getchar();	}
	return x*y;
}
void power(){
	ll cnt,x,sum,num=sqrtl(n)+1;
	for(ll i=2;i*i*i<=n;++i){
		if(vis[i])	continue;
		cnt=2;	x=i*i;
		if(x<=N)	vis.set(x);
		while(x*i<=n){
            sum=x;	++cnt;	x=x*i;
            if(x/i!=sum)	break;
			if(cnt>=k)	++ans;
			if(x<=N)	vis.set(x);
			if((ll)sqrtl(x)*sqrtl(x)==x)	++tot;
		}
	}
}
int main(){
	//freopen("power.in","r",stdin);
	//freopen("power.out","w",stdout);
	n=read(),k=read();
	if(k==1){	printf("%lld",n);	}
	else{
		power();
		if(k>=3)	printf("%lld",ans);
		else	printf("%lld",(ll)sqrtl(n)+ans-tot-1);
	}
	return 0;
}
2023/3/29 17:03
加载中...