题目链接
LibreOj#6235区间素数个数
思路
用min_25筛的前半部分解决，有点类似DP融合埃筛的解法
根据这个式子，举一个例子让我们更好理解这个式子
g(10,0)=9;
因为还没有筛选过依次，所以等于9
g(10,1)=g(10,0)-g(5,0)-g(1,0)=9-4-0=5;
筛选过依次之后把以2为最小质因子的数(4,6,8,10)给筛掉了剩下5.这里要注意，我们要用到g(5,0)与g(1,0)所以我们每次处理的时候不能只处理g(10)的。
g(10,2)=g(10,1)-g(3,1)-g(2,0)=5-0-1=4;
这里用到了g(3,1)与g(2,0)需要在上面处理好
g(10,3)=g(10,2)-g(5,2)-g(3,1)=4-0-0=4;
最后一步就不需要了，因为后面两个式子一定等于0,这是因为$prime_3^2=5^2>10$了，所以25之内的合数都已经被排除掉了，就不需要再考虑了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 4e5+10;
ll n,g[N<<1],a[N<<1];
int id,cnt,sn,prime[N];
ll Id(ll x){return x<=sn?x:id-n/x+1;}
int main()
{
scanf("%lld",&n);
sn=sqrt(n);
for(ll i=1;i<=n;i=a[id]+1)a[++id]=n/(n/i),g[id]=a[id]-1;
for(ll i=2;i<=sn;i++)if(g[i]!=g[i-1])
{
prime[++cnt]=i;
ll sum =1ll*i*i;
for(int j=id;a[j]>=sum;j--)g[j]-=g[Id(a[j]/i)]-g[i-1];
}
printf("%lld\n",g[id]);
}
|
题目链接
SPOJ-APS2
思路
刚学min25的时候写的一道题，很巧妙的思维题，用min25来维护质数的前缀和，以及个数，然后再埃筛的过程化的时候把合数的答案给加上去。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<cstdio>
#include<math.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const int N = 1111115;
ll n,g[N<<1],a[N<<1],h[N<<1],t;
int id,cnt,sn,prime[N];
ll Id(ll x){return x<=sn?x:id-n/x+1;}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ull ans=0;
cnt=0;
id=0;
scanf("%lld",&n);
sn=sqrt(n);
for(ll i=1;i<=n;i=a[id]+1)a[++id]=n/(n/i),g[id]=(a[id]%2==0?(ull)a[id]/2*(a[id]+1):(ull)(a[id]+1)/2*a[id])-1,h[id]=a[id]-1;
for(ll i=2;i<=sn;i++)if(h[i]!=h[i-1])
{
prime[++cnt]=i;
ll sq=1ll*i*i;
for(ull j=id;a[j]>=sq;j--)
{
g[j]-=(g[t=Id(a[j]/i)]-g[i-1])*i;
h[j]-=(h[t]-h[i-1]);
if(j==id)ans=(ans+i*(h[t]-h[i-1]));
}
}
printf("%llu\n",ans+g[id]);
}
}
|