题目链接
Loj6235
思路
一道Min25筛的很基础的入门题。就是对g函数求和的操作。先对n分块，然后从小到达筛素数，然后从大到小对g进行处理，
因为这样就能滚动处理g数组，少了一维空间
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 316300;
ll a[maxn<<1];
ll prime[maxn],cnt;
ll g[maxn<<1];
ll sqr,id,n;
int Id(ll x){return x<=sqr?x:id-n/x+1;}
int main()
{
scanf("%lld",&n);
ll sn = sqrt(n);
sqr=sn;
for(ll i=1;i<=n;i=a[id]+1)
{
a[++id]=n/(n/i);
g[id]=a[id]-1;
}
for(ll i=1;i<=sn;i++)if(g[i]!=g[i-1])
{
prime[cnt++]=i;
ll sq = 1ll*i*i;
for(ll j=id;a[j]>=sq;j--)
{
g[j]-=g[Id(a[j]/i)]-(cnt-1);
}
}
cout<<g[id]<<endl;
}
|