仅有30分,6个AC,3个WA,剩下的都是RE。哪位大佬可以不吝赐教,“传道授业解惑”?余不耻相师。
#include<cstdio>
constexpr int N=1e8+1;
bool not_prime[N];
int time,n,k;
void sushu();
int power(const int &m);
int main()
{
scanf("%d %d",&n,&k);
sushu();
printf("%d",time);
}
int power(const int &m)//快速幂
{
int d=m;
int a=k;
while(a)
{
d=d*d;
if(a&1)
{
--a;
d*=m;
//continue;
}
if(d>n) return 0;
a>>=2;
}
//printf("%d %d\n",m,d);
return d;
}
void sushu()//类似于埃氏筛
{
if(k==1)
{
time=n;
return;
}
if(n) time=1;
for(int i=2;i<=n;++i)
{
if(not_prime[i]) continue;
int pow=power(i);
if(!pow) return;
for(;pow<=n;pow*=i)
if(!not_prime[pow])//避免重复计数
{
not_prime[pow]=true;
++time;
}
}
return;
}