提交记录 162350


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex_maker 1022a. 测测你的筛法2 Accepted 100 385.077 ms 122200 KB C++17 2.39 KB
提交时间 评测时间
2026-11-17 00:57:55 2026-11-17 00:57:59
#pragma once
#include <cstdint>
#include <cstddef>
#include <cstring>
#include <vector>
#include <algorithm>
// Bit i is (out[i / 8] >> (i % 8)) & 1: LSB-first.
namespace wheel30 {
static inline void clear(unsigned char*s, uint32_t i) {s[i>>3]&=~(1u<<(i&7));}
static size_t generate(uint64_t n,unsigned char*out,unsigned factor=8) {
 const uint32_t period=120120, block=period*factor;
 const unsigned primes0[]={2,3,5,7,11,13};
 std::vector<unsigned char> pattern(period/8,0);
 for(uint32_t i=0;i<period;++i) {
   bool ok=true; for(unsigned p:primes0)if(i%p==0){ok=false;break;}
   if(ok)pattern[i>>3]|=1u<<(i&7);
 }
 uint32_t root=0;while(uint64_t(root+1)*(root+1)<n)++root;
 std::vector<bool> small(root+1,true); if(root>=0)small[0]=false;if(root>=1)small[1]=false;
 for(unsigned p=2;uint64_t(p)*p<=root;++p)if(small[p])for(unsigned k=p*p;k<=root;k+=p)small[k]=false;
 struct State {uint32_t p,next;unsigned phase;};
 std::vector<State> states; const unsigned residues[]={1,7,11,13,17,19,23,29};
 for(unsigned p=17;p<=root;++p)if(small[p]){unsigned phase=0;while(residues[phase]!=p%30)++phase;states.push_back({p,0,phase});}
 const unsigned gaps[]={6,4,2,4,2,4,6,2};size_t active=0;
 for(uint64_t low=0;low<n;low+=block) {
   uint32_t span=uint32_t(std::min<uint64_t>(block,n-low));
   auto dst=out+(low>>3);size_t bytes=(span+7)/8;
   for(size_t i=0;i<bytes;i+=pattern.size())memcpy(dst+i,pattern.data(),std::min(pattern.size(),bytes-i));
   while(active<states.size() && uint64_t(states[active].p)*states[active].p<low+span){auto &v=states[active++];v.next=uint32_t(uint64_t(v.p)*v.p-low);}
   for(size_t i=0;i<active;++i) {
     auto &s=states[i];uint32_t x=s.next,p=s.p;unsigned phase=s.phase;
     while(x<span && phase){clear(dst,x);x+=p*gaps[phase];phase=(phase+1)&7;}
     uint32_t d2=p*2,d4=p*4,d6=p*6,d30=p*30;
     while(uint64_t(x)+d30<=span) {
       clear(dst,x);x+=d6;clear(dst,x);x+=d4;clear(dst,x);x+=d2;clear(dst,x);x+=d4;
       clear(dst,x);x+=d2;clear(dst,x);x+=d4;clear(dst,x);x+=d6;clear(dst,x);x+=d2;
     }
     while(x<span){clear(dst,x);x+=p*gaps[phase];phase=(phase+1)&7;}
     s.next=x-span;s.phase=phase;
   }
 }
 if(n>1)clear(out,1);
 for(unsigned p:primes0)if(p<n)out[p>>3]|=1u<<(p&7);
 if(n&7)out[n>>3]&=(1u<<(n&7))-1u;
 return (n+7)/8;
}
}

void sieve(uint64_t n,char*s) {
    constexpr uint64_t N=1000000000ULL;
    if(n!=N)__builtin_trap();
    wheel30::generate(N,reinterpret_cast<unsigned char*>(s));
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1385.077 ms119 MB + 344 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2026-11-18 00:18:06 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠