就。。。就交上去会T,然后极限数据跑不过去。
用的WheelF (绝对不是F后面不会拼了) ,然后块长用的 2∗3∗5∗7 (前二三四个质数都试过了但是都会T),应该就是筛法这里的问题,想请诸位神仙帮忙康康这个东西是复杂度假了还是纯粹我人菜常大(
const int len=2*3*5*7;
const int lim=4,limp=7;
int LIM=0;
bool ip[len+10];
bool p[len+10];
int P[10020];
int cpt=0;
int mk[len+10];
int cmt=0;
bool np[len+10];
unsigned int ans=0;
unsigned int A,B,C,D;
inline unsigned int calc(unsigned int x){
return A*x*x*x+B*x*x+C*x+D;
}
inline void WF(int n){
memset(ip,1,sizeof(ip));
for(int i=2;i<=len;i++){
if(!p[i]){
P[++cpt]=i;
if(i<=limp)
ip[i]=0;
}
for(int j=1;j<=cpt;j++){
if(P[j]*i>len)break;
int t =P[j]*i;
p[t]=1;
if(P[j]<=limp)ip[t]=0;
if(i%P[j]==0)break;
}
}
for(int i=1;i<=len;i++)
if(ip[i])mk[++cmt]=i;
for(int o=1;o*len<=n;o++){
int st=o*len,ed=(o+1)*len-1;
memcpy(np,ip,sizeof(ip));
for(int j=lim+1;j<=cpt&&P[j]*P[j]<=ed;j++){
int t=max((st+P[j]-1)/P[j],P[j])*P[j],d=P[j]<<1;
if(!(t&1))t+=P[j];
for(int i=t-st;i<len;i+=d)
np[i]=0;
}
for(int i=1;i<=cmt;i++)
if(np[mk[i]]&&(mk[i]+st)<=LIM)P[++cpt]=mk[i]+st;
else if(np[mk[i]]&&mk[i]+st<=n)ans+=(n/(mk[i]+st))*calc(mk[i]+st);
}
}