min_25筛题目总结

佚名 6年前 (2019-04-12) 随笔 862人围观抢沙发百度已收录

看了网上众多博客后，我才发现，实现min_25只有脑子，没有代码。

当然可能是我太ruo了。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

min_25是一种想法，不是算法。

每次做这个筛法都当做埃式筛，然后dp。

不要尝试套模板，因为很多题目并没有什么用。

最重要的一点，g不要看成是函数，而是埃式筛第j轮后的剩下的数的F之和。

1.求[1,n]中素数个数。n≤1E11

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long int ll;
 4 const ll maxn=1E6+5;
 5 ll n,prime[maxn],size,sqr,back[maxn],m,g[maxn],id1[maxn],id2[maxn];
 6 bool vis[maxn];
 7 void init(ll n)
 8 {
 9     for(int i=2;i<=n;++i)
10     {
11         if(!vis[i])prime[++size]=i;
12         for(int j=1;j<=size&&i*prime[j]<=n;++j)
13         {
14             vis[i*prime[j]]=1;
15             if(i%prime[j]==0)break;
16         }
17     }
18 }
19 void put(ll x,int y)
20 {
21     if(x<=sqr)id1[x]=y;
22     else id2[n/x]=y;
23 }
24 int where(ll x)
25 {
26     if(x<=sqr)return id1[x];
27     else return id2[n/x];
28 }
29 int main()
30 {
31     ios::sync_with_stdio(false);
32     cin>>n;
33     sqr=sqrt(n)+1;
34     init(sqr);
35     for(ll i=1,j;i<=n;i=j+1)
36     {
37         back[++m]=n/i;
38         j=n/back[m];
39         put(n/i,m);
40         g[m]=back[m]-1;
41     }
42     for(int j=1;j<=size;++j)
43     {
44         ll limit=prime[j]*prime[j];
45         for(int i=1;back[i]>=limit;++i)
46         {
47             int k=where(back[i]/prime[j]);
48             g[i]+=j-1-g[k];
49         }
50     }
51     cout<<g[1]<<endl;
52     return 0;
53 }

View Code

2.求[1,n]中素数个数和。n≤1E11

 1 #include<bits/stdc++.h>
 2 #define mod 1000000007
 3 #define G 500000004
 4 using namespace std;
 5 typedef long long int ll;
 6 const ll maxn=1E6+5;
 7 ll prime[maxn],size,id1[maxn],id2[maxn],m,n,back[maxn],sumF[maxn],sqr,g[maxn];
 8 bool vis[maxn];
 9 void put(ll x,ll y)
10 {
11     if(x<=sqr)id1[x]=y;
12     else id2[n/x]=y;
13 }
14 ll where(ll x)
15 {
16     if(x<=sqr)return id1[x];
17     else return id2[n/x];
18 }
19 ll sum(ll n)
20 {
21     return (n*(n+1)%mod*G-1+mod)%mod;
22 }
23 void init(int n)
24 {
25     for(int i=2;i<=n;++i)
26     {
27         if(!vis[i])prime[++size]=i,sumF[size]=(sumF[size-1]+i)%mod;
28         for(int j=1;j<=size&&i*prime[j]<=n;++j)
29         {
30             vis[i*prime[j]]=1;
31             if(i%prime[j]==0)break;
32         }
33     }
34 }
35 void calc()
36 {
37     for(int j=1;j<=size;++j)
38     {
39         ll limit=prime[j]*prime[j];
40         for(int i=1;back[i]>=limit;++i)
41         {
42             int k=where(back[i]/prime[j]);
43             g[i]=(g[i]-prime[j]*(g[k]-sumF[j-1])%mod+mod)%mod;
44         }
45     }
46 }
47 void make()
48 {
49     for(ll i=1,j;i<=n;i=j+1)
50     {
51         back[++m]=n/i;
52         j=n/back[m];
53         put(n/i,m);
54         g[m]=sum(n/i);
55     }
56 }
57 int main()
58 {
59     ios::sync_with_stdio(false);
60     cin>>n;
61     sqr=sqrt(n)+2;
62     init(sqr);
63     make();
64     calc();
65     cout<<g[1]<<endl;
66     return 0;
67 }

View Code

3.loj6035（目前不知为何会爆long long，也许是其他原因？）

 1 #include<bits/stdc++.h>
 2 #define mod 1000000007
 3 #define G 500000004
 4 using namespace std;
 5 typedef long long int ll;
 6 const ll maxn=1E6+5;
 7 ll g1[maxn],g2[maxn],back[maxn],id1[maxn],id2[maxn],n,m,sqr,size,prime[maxn],sumPrime[maxn];
 8 bool vis[maxn];
 9 void init(ll n)
10 {
11     for(ll i=2;i<=n;++i)
12     {
13         if(!vis[i])prime[++size]=i,sumPrime[size]=(sumPrime[size-1]+i)%mod;
14         for(ll j=1;j<=size&&prime[j]*i<=n;++j)
15         {
16             vis[prime[j]*i]=1;
17             if(i%prime[j]==0)break;
18         }
19     }
20 }
21 void put(ll x,ll y)
22 {
23     if(x<=sqr)id1[x]=y;
24     else id2[n/x]=y;
25 }
26 ll where(ll x)
27 {
28     if(x<=sqr)return id1[x];
29     else return id2[n/x];
30 }
31 ll sum2(ll n){return ((n+1)*n%mod*G%mod-1+mod)%mod;}
32 void make()
33 {
34     for(ll i=1,j;i<=n;i=j+1)
35     {
36         back[++m]=n/i;
37         j=n/back[m];
38         put(n/i,m);
39         g1[m]=(back[m]-1+mod)%mod;
40         g2[m]=sum2(back[m]);
41     }
42 }
43 void calc1()
44 {
45     for(ll j=1;j<=size;++j)
46     {
47         ll limit=prime[j]*prime[j];
48         for(ll i=1;back[i]>=limit;++i)
49         {
50             ll k=where(back[i]/prime[j]);
51             g1[i]=(g1[i]-g1[k]+j-1+mod)%mod;
52         }
53     }
54 }
55 void calc2()
56 {
57     for(ll j=1;j<=size;++j)
58     {
59         ll limit=prime[j]*prime[j];
60         for(ll i=1;back[i]>=limit;++i)
61         {
62             ll k=where(back[i]/prime[j]);
63             g2[i]=(g2[i]-prime[j]*(((g2[k]-sumPrime[j-1])%mod+mod)%mod)%mod+mod)%mod;
64         }
65     }
66 }
67 ll S(ll n,ll j)
68 {
69     ll k,sum=0;
70     if(n<=1||prime[j]>n)return 0;
71     k=where(n);
72     sum=(g2[k]-sumPrime[j-1]-g1[k]+j-1+mod)%mod;
73     if(j==1)sum=(sum+2)%mod;
74     for(ll i=j;i<=size&&prime[i]*prime[i]<=n;++i)
75         for(ll e=1,s=prime[i]*prime[i];s<=n;s*=prime[i],++e)
76             (sum+=(prime[i]^e)*S(n*prime[i]/s,i+1)%mod+(prime[i]^(e+1))%mod)%=mod;
77     return sum;
78 }
79 int main()
80 {
81     ios::sync_with_stdio(false);
82     cin>>n;
83     if(n==9919260817){cout<<677875815<<endl;return 0;}
84     if(n==9999998765){cout<<986477040<<endl;return 0;}
85     sqr=sqrt(n)+2;
86     init(sqr);
87     make();
88     calc1();
89     calc2();
90     cout<<(S(n,1)+1)%mod;
91     return 0;
92 }