杜教筛

又写了一个模板。。。

不过直接地发现我好菜

贴个链接:luoguP4213

简直就是一个模板裸题妈呀好难

杜教筛我好像结论能背了……

$Φ_n=\dfrac{n(n+1)}2-\sum_{i=2^n}Φ_{⌊ni⌋}\\M_n=1−\sum_{i=2}^nM_{⌊ni⌋}$

第一次我写了一个这样子的程序:

1
2
3
4
5
6
7
8
9
10
for(int i=1;i<=n;i++)
{
phi[i]=i*(i+1)/2;
mu[i]=1;
for(int j=2;j<=i;j++)
{
phi[i]-=phi[i/j];
mu[i]-=mu[i/j];
}
}

然后预处理直接$O(n^2)$挂了

然后一脸懵

还有这样欺骗人的吗?

冷静下来找错

$O((n^\frac23)2)=O(n^\frac43)$,我写了什么??

赶紧整除分块

于是依然是$O((n^\frac23)^\frac32)=O(n)$预处理

然后在 大的gkk的帮助下

知道了怎么$O(n^{\frac23})$预处理

就是$O(n^{\frac23})$求$ϕ_i,μ_i$

于是我又发现不会线性筛$ϕ,μ$

只好根据定义:

1
2
3
4
5
6
7
8
9
10
fr(i,2,k)
if(phi[i]==i)
fr(j,1,k/i)
{
phi[j*i]=phi[j*i]/i*(i-1);
if(j%i)
mu[j*i]*=-1;
else
mu[j*i]=0;
}

于是无数TLE

想着苟上60看代码去

接着看了几个网上的比gkk还丑的代码,假装会了

于是就有了这个代码:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#define k 5000000
int t,n;
int smu[k+10],mu[k+10],p[k],m;
long long sphi[k+10],phi[k+10];
long long getsphi(long long n)
{
if(n<=k)return sphi[n];
long long l=2,r;
long long ans=n*(n+1)/2;
while(l<=n)
{
r=n/(n/l);
ans-=getsphi(n/l)*(long long)(r-l+1);
l=r+1;
}
return ans;
}
int getsmu(long long n)
{
if(n<=k)return smu[n];
long long l=2,r;
int ans=1;
while(l<=n)
{
r=n/(n/l);
ans-=getsmu(n/l)*(r-l+1);
l=r+1;
}
return ans;
}
int main()
{
t=read();
phi[1]=mu[1]=1;
fr(i,2,k)
{
if(!phi[i])
{
phi[i]=i-1;
p[++m]=i;
mu[i]=-1;
}
fr(j,1,m)
if(p[j]*i>k)break;
else
if(i%p[j])
{
mu[i*p[j]]=-mu[i];
phi[i*p[j]]=phi[i]*(p[j]-1);
}
else
{
mu[i*p[j]]=0;
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
fr(i,1,k)
{
sphi[i]=sphi[i-1]+phi[i];
smu[i]=smu[i-1]+mu[i];
}
while(t--)
{
n=read();
printf("%lld %d\n",getsphi(n),getsmu(n));
}
return 0;
}

看了别人(luogu上)的一个代码

于是知道了应该怎么做(我太菜了!)

先给个代码

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
long long getsphi(long long n,long long nn)
{
if(n<=k)return sphi[n];
if(ssphi[nn])return ssphi[nn];
long long l=2,r;
long long ans=n*(n+1)/2;
while(l<=n)
{
r=n/(n/l);
ans-=getsphi(n/l,nn*l)*(long long)(r-l+1);
l=r+1;
}
ssphi[nn]=ans;
return ans;
}
int getsmu(long long n,long long nn)
{
if(n<=k)return smu[n];
if(ssmu[nn])return ssmu[nn];
long long l=2,r;
int ans=1;
while(l<=n)
{
r=n/(n/l);
ans-=getsmu(n/l,nn*l)*(r-l+1);
l=r+1;
}
ssmu[nn]=ans;
return ans;
}

多记录点不好吗??

最后的代码:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#define k 3000000
int t,n;
int smu[k+10],ssmu[k+10],mu[k+10],p[k],m;
long long sphi[k+10],phi[k+10],ssphi[k+10];
long long getsphi(long long n,long long nn)
{
if(n<=k)return sphi[n];
if(ssphi[nn])return ssphi[nn];
long long l=2,r;
long long ans=n*(n+1)/2;
while(l<=n)
{
r=n/(n/l);
ans-=getsphi(n/l,nn*l)*(long long)(r-l+1);
l=r+1;
}//杜教筛(整除分块)
ssphi[nn]=ans;//记录下来
return ans;
}
int getsmu(long long n,long long nn)
{
if(n<=k)return smu[n];
if(ssmu[nn])return ssmu[nn];
long long l=2,r;
int ans=1;
while(l<=n)
{
r=n/(n/l);
ans-=getsmu(n/l,nn*l)*(r-l+1);
l=r+1;
}//同上
ssmu[nn]=ans;
return ans;
}
int main()
{
t=read();
phi[1]=mu[1]=1;//初始化1的
fr(i,2,k)
{
if(!phi[i])//质数的phi不会预先处理
{
phi[i]=i-1;
p[++m]=i;//记录质数
mu[i]=-1;
}
fr(j,1,m)
if(p[j]*i>k)break;//大于了后面也一定会大于
else
if(i%p[j])
{
mu[i*p[j]]=-mu[i];
phi[i*p[j]]=phi[i]*(p[j]-1);
}
else
{
mu[i*p[j]]=0;
phi[i*p[j]]=phi[i]*p[j];
break;//后面的一定被处理过
}//定义推
}
fr(i,1,k)
{
sphi[i]=sphi[i-1]+phi[i];//前缀处理
smu[i]=smu[i-1]+mu[i];
}
while(t--)
{
n=read();
fr(i,1,k)ssmu[i]=ssphi[i]=0;//清0,因为对于每个n,phi(n/i)不一样
printf("%lld %d\n",getsphi(n,1),getsmu(n,1));
}
return 0;
}