题解 P2158 【[SDOI2008]仪仗队】

[题目](https://www.luogu.org/problemnew/show/P2158) --- update on 2023.09.06 加入了一个适用性比较广的筛法，在文章末。 --- 本文进行了一定的更新 1. 优化了 Markdown 中 Latex 语句的运用，加强了可读性 2. 补充了“我们仍不曾知晓得 消失的 性质5 ”，加强了推导的严谨性 3. 介于使用了新的推导方法，调整了推导顺序 4. 补充了关于线性筛的欧拉函数性质8 5. **又又又又又** 修改了部分错误（工程量太大，老是出错） 6. 安利了 3b1b 的链接，虽然与本文章无关，但对我们的思维提升很有利 7. 将欧拉函数的定义正确修改 8. 减少了 $ans(n)$ 推导公式的争议性，加强了推导过程的严谨性 9. 更新了 python 代码，方便跟大家学习~~装逼~~ **【分析】** -- 我们设 **左数第 $a$ 列，后数第 $b$ 列的同学，坐标为 $(a-1,b-1)$ ** 那么，C君的坐标为 $(0,0)$。 现在我们即对题目完成建模：在一个从 $(0,0)$ 到 $(n-1,n-1)$ 的点阵中，有多少点能被 $(0,0)$ 点“看到” ？ --- 根据图像，易得出，所有的点都是关于 $y=x$ 对称的(这个性质我们待会儿要用到)。 根据题目，如何判定一个点是否看得到呢？ 我们假设对于一个存在的点 $(x,y)$，那么，根据图像的直观意义，便可以知道，原点和该点连线方向往后的每一个点，都是看不到的。 即对任意整点 $(x,y)$，点 $(\lambda x,\lambda y),(\lambda>1)$ 是看不到的。 我们可以显然发现：$gcd(\lambda x,\lambda y)=\lambda gcd(x,y)>\lambda\cdot1=\lambda>1$。 也就是说，对于一个点 $(x,y)$ ，当 $gcd(x,y) \neq 1$ 时这个点看不到。 而对于任意满足 $gcd(x,y)=1$ 的点 $(x,y)$ ，若它会被遮挡，则必定有整点 $({x\over m},{y\over m}),(m>1)$ 存在。 根据 $gcd(x,y)=1$ ，我们能发现这样的点不存在 所以我们得出结论：**一个点 $(x,y)$ 能被看到，当且仅当 $gcd(x,y)=1$** --- 因此，题目对于给定的 $n$ 所求的点数 $ans(n)$ 即满足 $ans(1)=0$ $\displaystyle ans(n)= \sum_{x=0}^{n-1} \sum_{y=0}^{n-1} [gcd(x,y)=1],n \geq 2$ >当然，我们知道 $gcd(0,i)=gcd(i,0)=i$ 显然，这个式子可以展开为 $\displaystyle ans(n)=\sum_{x=0}^{n-1} \sum_{y=0}^{x-1}[gcd(x,y)=1]+ \sum_{x=0}^{n-1} \sum_{y=x}^x [gcd(x,y)=1] + \sum_{x=0}^{n-1} \sum_{y=x+1}^{n-1}[gcd(x,y)=1],n \geq 2$ 又因为 $y=x$ 上能被看到的点只有点 $(1,1)$ ，所以我们可以直接考虑这个点，然后忽略这条直线了 因此，我们可以将这个式子化简为 $\displaystyle ans(n)=\sum_{x=0}^{n-1} \sum_{y=0}^{x-1}[gcd(x,y)=1]+ 1 + \sum_{x=0}^{n-1} \sum_{y=x+1}^{n-1}[gcd(x,y)=1],n \geq 2$ 由文章最上方写的图像的原理，我们可以知道 $\displaystyle \sum_{x=0}^{n-1} \sum_{y=0}^{x-1}[gcd(x,y)=1]= \sum_{x=0}^{n-1} \sum_{y=x+1}^{n-1}[gcd(x,y)=1]$ 因此 $\displaystyle ans(n)=2\sum_{x=0}^{n-1} \sum_{y=0}^{x-1}[gcd(x,y)=1]+1,n \geq 2$ 又因为根据欧拉函数 $\boldsymbol \varphi (n)$ 的定义，为小于等于 $n$ 的自然数中，与 $n$ 互质的数的个数 >数 $a$ 与 $b$ 互质，当且仅当 $gcd(a,b)=1$ 。因此得出 $1$ 与所有数互质 即 $\displaystyle \boldsymbol \varphi (n)=\sum_{i=0}^{n-1} [gcd(i,n)=1]$ 因此，我们可以将式子简化为： $\displaystyle ans(n)=2\sum_{x=0}^{n-1} \boldsymbol \varphi(x) +1,n \geq 2$ 个人习惯这样表示：$\displaystyle \Phi(n)=\sum_{i=0}^n\boldsymbol\varphi(i)$ 所以，式子我们也可以这么写： $\displaystyle ans(n)=2\Phi(n-1) +1,n \geq 2$ 终于，我们得到了本题的答案： $\begin{cases} ans(1)=0 \\\\ \displaystyle ans(n)=2\Phi(n-1) +1,n \geq 2 \end{cases}$ --- 那么，这里对于如何求 $\boldsymbol \varphi(n)$ 做一个讲解，已经掌握的大佬们请直接跳过。 首先，$\boldsymbol \varphi(n)$ 的定义是在小于 $n$ 的正整数中，与 $n$ 互质的数的个数。 因此，我们先考虑一下，假设存在一个质数 $p$。 那么， $p$ 的因数只有 $1$ 和 $p$。 在小于 $p$ 的正整数中，不存在任何数含有因数 $p$； 因此， $p$ 和任意比它小的正整数都互质。 也就是**性质1 $\boldsymbol \varphi(p)=p-1$ ( $p-1$ 个数比它小)** --- 接下来，我们考虑 $p^k,k \in Z_+$ 且 $k>1$ $p^k$ 有且仅有质因数 $p$ 且比它小的 $(p^k-1)$ 个数中，存在一下几个数也含有质因数 $p$ $p\ ,\ 2p\ ,\ 3p\ ,\ 4p\ \dots\ (p^{k-1}-1)p$ 共 $(p^{k-1}-1)$ 个数 因此，剩余的 $(p^k-1)-(p^{k-1}-1)=(p^k-p^{k-1})$ 个数都与之互质 于是我们可以把 $k=1$ 看成这个的一个特例 于是我们得到**性质2 $\boldsymbol \varphi(p^k)=p^k-p^{k-1},k \in Z_+$** 同时，又因为 $\boldsymbol \varphi(p^{k+1})=p^{k+1}-p^k=p\times(p^k-p^{k-1})$ 所以，还能得到**性质3 $\boldsymbol \varphi(p^{k+1})=p \times \boldsymbol \varphi(p^k)$** --- 接下来，我们考虑 $\boldsymbol \varphi(p_1^{k_1} p_2^{k_2})$ $(p_1 \neq p_2$ 且 $p_1,p_2$ 为质数 $,k_1,k_2 \in Z_+)$ 那么，在比它小的 $(p_1^{k_1} p_2^{k_2}-1)$ 个数中 $p_1\ ,\ 2p_1\ ,\ 3p_1\ ,\ 4p_1\ \dots\ (p_1^{k_1-1} p_2^{k_2}-1)p_1$ 共 $(p_1^{k_1-1} p_2^{k_2}-1)$ 个数与它的最大公因数中含 $p_1$ 同理，共 $(p_1^{k_1} p_2^{k_2-1}-1)$ 个数与它最大公因数含 $p_2$ 但是，这里还有这重复枚举 $p_1p_2\ ,\ 2p_1p_2\ ,\ 3p_1p_2\ ,\ 4p_1p_2\ \dots\ (p_1^{k_1-1} p_2^{k_2-1}-1)p_1p_2$ 共 $(p_1^{k_1-1} p_2^{k_2-1}-1)$ 个数被重复枚举 因此，根据容斥原理，我们可以得到 $\boldsymbol \varphi(p_1^{k_1}p_2^{k_2})$ $=(p_1^{k_1} p_2^{k_2}-1)-(p_1^{k_1-1} p_2^{k_2}-1)-(p_1^{k_1} p_2^{k_2-1}-1)+(p_1^{k_1-1} p_2^{k_2-1}-1)$ $=p_1^{k_1} p_2^{k_2}-p_1^{k_1-1} p_2^{k_2}-p_1^{k_1} p_2^{k_2-1}+p_1^{k_1-1} p_2^{k_2-1}$ $=p_1^{k_1}p_2^{k_2}(1-{1\over p_1}-{1\over p_2}+{1\over p_1p_2})$ $=p_1^{k_1}p_2^{k_2}(1-{1\over p_1})(1-{1\over p_2})$ $=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})$ 又因为根据**性质2**，有 $\boldsymbol \varphi(p_1^{k_1})=(p_1^{k_1}-p_1^{k_1-1}),\boldsymbol \varphi(p_2^{k_2})=(p_2^{k_2}-p_2^{k_2-1})$ 因此，带入上式得到**性质4 $\boldsymbol \varphi(p_1^{k_1}p_2^{k_2})=\boldsymbol \varphi(p_1^{k_1})\boldsymbol \varphi(p_2^{k_2})$** --- **性质5** 的证明略长（因为是自己想的，所以可能有些繁琐），我放到代码下面，感兴趣的朋友们可以自行查看，我这边直接给出证明结果： 当 $\displaystyle n=\prod_{i=1}^mp_i^{k_i}$ 时 $\displaystyle \boldsymbol \varphi(n)=n\prod_{i=1}^m(1-{1\over p_i})$ 其中，**性质5** 的变式 $\displaystyle \boldsymbol \varphi(n)=n\prod_{i=1}^m({p_i-1\over p_i})$ 常用来求单个自变量的欧拉函数值 --- 我们代入 $\displaystyle n=\prod_{i=1}^mp_i^{k_i}$ 得到 $\displaystyle \boldsymbol \varphi(n)=n\prod_{i=1}^m(1-{1\over p_i})=\prod_{i=1}^mp_i^{k_i}\times \prod_{i=1}^m(1-{1\over p_i})=\prod_{i=1}^m[p_i^{k_i}(1-{1\over p_i})]$ $\therefore \displaystyle \boldsymbol \varphi(n)=\prod_{i=1}^m(p_i^{k_i}-p_i^{k_i-1})$ 根据 $\boldsymbol \varphi(p_i^{k_i})$ 的定义，我们可以知道**性质6 $\displaystyle \boldsymbol \varphi(n)=\prod_{i=1}^m\boldsymbol \varphi(p_i^{k_i})$** 代入**性质一**可化简得 $\displaystyle \boldsymbol \varphi(n)=\prod_{i=1}^m(p_i^{k_i}-p_i^{k_i-1})$ --- 我们再令 $\displaystyle q=\prod_{i=1}^a p_i^{k_i},r=\prod_{i=a+1}^m p_i^{k_i}$，显然 $gcd(q,r)=1$。 $\displaystyle \boldsymbol \varphi(q)=\prod_{i=1}^a\boldsymbol \varphi(p_i^{k_i}),\boldsymbol \varphi(r)=\prod_{i=a+1}^m\boldsymbol \varphi(p_i^{k_i}),qr=\prod_{i=1}^a p_i^{k_i}\times\prod_{i=a+1}^m p_i^{k_i}=\prod_{i=1}^m p_i^{k_i}=n$ $\therefore \displaystyle \boldsymbol \varphi(qr)=\boldsymbol \varphi(n)=\prod_{i=1}^m\boldsymbol \varphi(p_i^{k_i})=\prod_{i=1}^a\boldsymbol \varphi(p_i^{k_i})\times \prod_{i=a+1}^m\boldsymbol \varphi(p_i^{k_i})=\boldsymbol \varphi(q)\boldsymbol \varphi(r)$ 这就是欧拉函数的**性质7 $\forall gcd(a,b)=1\Leftrightarrow\boldsymbol\varphi(ab)=\boldsymbol\varphi(a)\boldsymbol\varphi(b)$** 因为这个特点，我们称呼欧拉函数为积性函数，即满足 $\forall gcd(a,b)=1\Leftrightarrow \boldsymbol f(ab)=\boldsymbol f(a)\boldsymbol f(b)$ 的函数 >这里补充一个 **完全积性函数** ：$\forall a,b\in R\Leftrightarrow \boldsymbol f(ab)=\boldsymbol f(a)\boldsymbol f(b)$ ，例如函数 $\boldsymbol {id}(x)=x$ 到此，对于本蒟蒻所知的 $\boldsymbol \varphi(n)$ 函数性质已经全部讲完 ~~(愣是码了不知道多少天......)~~ --- 那么，我们开始讲线性筛 线性筛用到了 **性质3** 和 **性质7** 的结论 ~~(意思不需要懂证明)~~ 根据 **性质7** $\boldsymbol \varphi(i\times prime_j)=\boldsymbol \varphi(i)\times \boldsymbol \varphi(prime_j)(prime_j\nmid i)$ 而满足 $prime_j\mid i$ 时，令 $k$ 为 $i$ 中不含 $prime_j$ 的最大因数，且令 $i=k\times prime_j^t$ $\therefore \boldsymbol \varphi(i\times prime_j)=\boldsymbol\varphi(k\times prime_j^t\times prime_j)=\boldsymbol \varphi(k)\boldsymbol \varphi(prime_j^{t+1})$ $\therefore \boldsymbol \varphi(i\times prime_j)=\boldsymbol \varphi(k)\times prime_j\times \boldsymbol \varphi(prime_j^t)=prime_j\times \boldsymbol \varphi(k\times prime_j^t)$ 根据前文定义得 $\boldsymbol \varphi(i\times prime_j)=prime_j\times \boldsymbol\varphi(i)$ 再代入**性质1**，并归纳起来说，就是 $\boldsymbol \varphi(i\times prime_j)=\begin{cases}\boldsymbol \varphi(i)\times (prime_j-1),prime_j\nmid i\\\ \\\boldsymbol \varphi(i)\times prime_j,\qquad\ \ prime_j\mid i\end{cases}$ ~~其实这是**性质8**~~ --- 参考素数的线性筛，为了保证时间的线性，那么，就必须保证每个数只筛到一次 为了保证每个数只被筛到一次，一定要保证其只被其最小素因数筛到过 那么，线性筛 $\boldsymbol \varphi(n)$ 也是一样 对于枚举到的 $i(i \geq 2)$，我们用 $pf_i$ 储存它的最小质因数 倘若出现 $pf_i=0$，则说明 $i$ 的最小质因数在 $2$~$(i-1)$ 都并未出现 因此，足以证明 $i$ 为质数 所以，$pf_i=i,\boldsymbol \varphi(i)=i-1$，并将 $i$ 存入到质数表中 接下来，无论 $i$ 是否为质数，直接在质数表中枚举质数 $prime_j$ 倘若 $prime_j \leq pf_i$ 那么，显然 $pf_{i \times prime_j}=prime_j$ 若 $prime_j|i$ 那么就说明 $i$ 含有质因数 $prime_j$ 因此，$\boldsymbol \varphi(i \times prime_j)=prime_j \times \boldsymbol \varphi(i)$ 否则，说明不含 则 $\boldsymbol \varphi(i \times prime_j)=\boldsymbol \varphi(prime_j) \times \boldsymbol \varphi(i)$ 倘若 $prime_j > pf_i$ 那么，数 $i\times prime_j$ 将被数 ${i \times prime_j \over pf_i}$ 筛到，这里可以直接开始跳出 最后，注意质数表的大小和 $i \times prime_j$ 的大小 我就是这个地方被卡了好多次...... --- **【代码】** -- 那本蒟蒻就放 ~~我码风极丑的~~ 代码了 新代码： ```cpp #include<cstdio> using namespace std; #define f(a,b,c,d) for(int a=b,c=d;a<=c;a++) int ans(int n){ if(n==1) return 0; int prime[40010]={0},cnt=0,fc[40010]={0},phi[40010]={0}; //这里 phi[n] 表示欧拉函数的前 n 项前缀和 phi[1]=1; f(i,2,I,n-1){ if(fc[i]==0){ prime[++cnt]=i; fc[i]=i; phi[i]=i-1; } f(j,1,J,cnt) if(prime[j]*i>n||prime[j]>fc[i]) break; else{ fc[prime[j]*i]=prime[j]; if(prime[j]<fc[i]) phi[prime[j]*i]=(prime[j]-1)*phi[i]; else phi[prime[j]*i]=prime[j]*phi[i]; } phi[i]+=phi[i-1]; } return (phi[n-1]<<1|1); } int main(){ int n; scanf("%d",&n); printf("%d", ans(n) ); return 0; } ``` 老代码： ```cpp #include<cstdio> using namespace std; #define f(a,b,c) for(int a=b;a<=c;a++) int main(){ int n,ans=3; int prime[5001]={0},size=0,pf[40001]={0},phi[40001]={0}; scanf("%d",&n); if(n^1){ f(i,2,n-1){ if(!pf[i]){ phi[i]=pf[i]=prime[size++]=i; phi[i]--; } ans+=(phi[i]<<1); f(j,0,size-1) if((prime[j]*i>n)|(prime[j]>pf[i])) break; else{ pf[i*prime[j]]=prime[j]; if(i%prime[j]) phi[i*prime[j]]=phi[i]*phi[prime[j]]; else phi[i*prime[j]]=phi[i]*prime[j]; } } printf("%d",ans); } else putchar('0'); return 0; } ``` Python 3 版代码 ~~（现学现卖，第一个python程序）~~ ```python n=int(input()) if n==1 : print(0) else: prime=[] phi=[] fc=[] for i in range(1,n+1): fc.append(0),phi.append(0) phi[1]=1 for i in range(2,n): if fc[i]==0 : prime.append(i) phi[i]=i-1 fc[i]=i; for p in prime : if p*i>=n : break else: fc[p*i]=p phi[p*i]=p*phi[i] if p<fc[i] : phi[p*i]-=phi[i] else: break phi[i]+=phi[i-1] ans=phi[n-1]<<1|1 print(ans) ``` 最后安利一下 [本蒟蒻的博客](https://www.luogu.org/blog/JustinRochester/#) ---- **【补充证明】** --- 该证明方法需要对集合、容斥原理、概率有一定的了解 同样地，我们再用容斥原理考虑一下 $n=p_1^{k_1}p_2^{k_2}p_3^{k_3}\dots p_m^{k_m}$ 或者本人比较喜欢这样书写：$\displaystyle n=\prod_{i=1}^m p_i^{k_i}$ 其中，保证 $\forall i\in[1,m]\bigcap Z$ 都有 $ p_i$ 为质数 方便起见，我们令 $U=[1,m]\bigcap Z$ 那么，$n$ 中与含因数 $p_i$ 的数都与 $n$ 不互质，它们一共有： $p_i\ ,\ 2p_i\ ,\ 3p_i\ \dots\ ({n\over p_i})p_i$ 共 $({n\over p_i})$ 个 扣除后剩余 $\displaystyle [n-\sum_{i=1}^m({n\over p_i})]$ 个数 但是，同时含 $p_ip_j$ 的在 $p_i$ 处扣除了一次， $p_j$ 处又扣除了一次，我们还得补回去，它们一共有： $p_ip_j\ ,\ 2p_ip_j\ ,\ 3p_ip_j\ \dots\ ({n\over p_ip_j})p_ip_j$ 共 $({n\over p_ip_j})$ 个 补充后为 $\displaystyle [n-\sum_{i=1}^m({n\over p_i})+\sum_{i=1}^m\sum_{j=i+1}^m({n\over p_ip_j})]$ 个数 但是，同时含 $p_ip_jp_k$ 的数又被多扣除了一次 你会发现，你扣除了一个数的，就要补充两个数的，接着就要扣除三个数的，然后补充四个数的...... 终于，根据容斥原理，$m$ 个数的不知道是扣除还是补充后，终于，没有任何重复或缺失了，但你也发现按这种方法无法表达。你陷入了一种只可意会不可言传的境界 能领略到欧拉函数的美妙是一件好事，但仅限于那种只可意会不可言传的境界是不够的，我们得想办法表达出来 --- 我们换个角度思考，只考虑 $p_i$ 的时候，我们相当于考虑了 $U$ 的所有单元素子集 只考虑 $p_ip_j$ 的时候，相当于考虑了 $U$ 的所有双元素子集 以此类推，考虑 $\displaystyle \prod_{i=1}^n p_i$ 的时候考虑了 $U$ 的 $n$ 元素子集 合起来，我们实际上考虑了 $U$ 的所有非空子集 那么，我们考虑 $T$ 为 $U$ 的所有非空子集的集合 (注意，$T$ 本身就是集合，但它的元素也是集合，它是集合的集合) 那么，$\displaystyle\boldsymbol\varphi(n)=n+\sum_{S\in T}[(-1)^{Card(S)}({n\over\prod_{i\in S}p_i})]$ >$Card(S)$ 表示集合 $S$ 的元素的数量 提取公因式 $n$ ，得到 $\displaystyle\boldsymbol\varphi(n)=n[1+\sum_{S\in T}{(-1)^{Card(S)}\over\prod_{i\in S}p_i}]$ 根据公式 $\displaystyle 1+\sum_{S\in T}{[(-1)^{Card(S)}\prod_{i\in S}p_i}]=\prod_{i\in U}(1-p_i)$ （该公式的证明我再往下放） 我们得到 $\displaystyle 1+\sum_{S\in T}{(-1)^{Card(S)}\over\prod_{i\in S}p_i}=1+\sum_{S\in T}{[(-1)^{Card(S)}\prod_{i\in S}({1\over p_i})}]=\prod_{i\in U}(1-{1\over p_i})$ 因此我们得到 $\displaystyle\boldsymbol \varphi(n)=n[1+\sum_{S\in T}{(-1)^{Card(S)}\over\prod_{i\in S}p_i}]=n\prod_{i\in U}(1-{1\over p_i})$ 根据前面关于 $U$ 的定义 ，我们得到**性质5 $\displaystyle \boldsymbol \varphi(n)=n\prod_{i=1}^m(1-{1\over p_i})$** --- （累成死狗ing） --- 关于公式 $\displaystyle 1+\sum_{S\in T}{[(-1)^{Card(S)}\prod_{i\in S}p_i}]=\prod_{i\in U}(1-p_i)$ 怎么来的，这里给出证明 正面证明这个公式是极其困难的，我们考虑用建模的方法证明： 假设有 $m$ 个相互独立的事件，它们发生的概率分别为 $p_1\ ,\ p_2\ ,\ p_3\ \dots\ p_m$ 那么，它们都不发生的概率就是 $\displaystyle \prod_{i=1}^m(1-p_i)$ 根据对 $U$ 的定义，它等于等式的右边 那么左边是什么呢？左边其实就是这个用容斥原理的展开 首先是 $1$ ，然后减去事件 $i$ 必定发生的概率，再补回 $i,j$ 事件必定发生的概率，再再扣除事件 $i,j,k$ 必定发生的概率...... 显然，我们用 [3b1b](https://space.bilibili.com/88461692?from=search&seid=3760714434062012953) 的方法证明了该式的正确性 ---- （完结撒花） --- update on 2023.09.06 ~~写这篇文章的时候我应该是高一高二，现在我已经研一了，时间过得真快~~ 鉴于有人在评论区表示“考场上想不到”、“代码效率低”、“理解难度大”、“看不懂” 确实，这个基于欧拉函数性质的筛法，其实并不适用于绝大部分的的积性函数；这里我们介绍一个适用性更广的线性筛法。其只需要用到性质2、6；即**积性函数在质数（及其幂次）的结果**，以及**积性**，这两个性质： 我们考虑在线筛积性函数的时候，除了维护其最小质因子，额外维护其除了最小质因子，是从哪个数字转移来的（不妨称为前继），记为 $fr_n$； 例如 $fr_{12}=fr_{2^2\times 3}=3, fr_{30}=fr_{2\times 3\times 5}=15,fr_{8}=fr_{2^3}=1$。 那么，我们就将数字 $n$ 成功地划分为了两部分：最小质因子的幂次 ${n\over fr_n}$，以及剩余的、与它互质的前继部分 $fr_n$ 基于此，积性函数可以直接转移： $\boldsymbol \varphi(n)=\boldsymbol \varphi({n\over fr_n})\cdot \boldsymbol \varphi(fr_n)$ 而我们仅需根据性质2直接递推积性函数在质数幂次的结果即可，代码如下： ```cpp int minp[MAXN];//最小质因子 int fr[MAXN];//前继 int prime[MAXN], cntprime;//质数列表 int phi[MAXN];//积性函数 inline void sieve_prime(int p, int n) {//处理质数的幂次 prime[++cntprime]=p;//记录新质数 phi[p]=p-1;//记录质数处的结果 minp[p]=p;//记录最小质因子 fr[p]=1;//记录从1转移而来 /* 这里我们为了防止溢出，则 p**k<=n 可以转化为 p**(k-1)<=n/p 以下p1表示p**(k-1), p2表示p**k */ for(int p1=p, p2=p*p, pn=n/p; p1<=pn; p1=p2, p2*=p) { phi[p2]=phi[p1]*p;//转移质数的幂次 minp[p2]=p; fr[p2]=1; } } inline void sieve(int n) { phi[1]=1; for(int i=2; i<=n; ++i) { if(!minp[i])//质数 sieve_prime(i, n); for(int j=1, x; j<=cntprime; ++j) if(prime[j]>minp[i] || (x=prime[j]*i)>n) break; else { minp[x]=prime[j];//记录最小质因子 fr[x]=(minp[i] == prime[j]?fr[i]:i); /* 当i的最小质因子和选中的质数相同时，x的前继和i的前继相同； 否则x的前继为i */ phi[x]=phi[x/fr[x]]*phi[fr[x]];//直接利用积性计算 } } } ``` 我们可以很简单地计算其复杂度： 对于所有的合数，其需要在内层 `for` 循环中被计算一次，这部分的复杂度是 $O(n)$ 的。 对于所有质数及其幂次，我们会在 `sieve_prime` 额外计算一次，然而这部分的数字个数是 $O(n)$ 的；又由于我们的转移为 $O(1)$，因此复杂度也是 $O(n)$。 因此，这个实现方法的总复杂度仍然为 $O(n)$，并且其仅需要质数幂次的部分，转移复杂度为 $O(1)$，这个条件显然还适用于莫比乌斯函数、除数个数函数、刘维尔函数等函数。 ~~或者是出题人构造的，奇奇怪怪的积性函数，例如 $\boldsymbol f(p^e)=p\oplus e$ 这种。~~ --- 此外，对于除数幂和函数 $\displaystyle \boldsymbol \sigma_k(n)=\sum_{d\mid n}d^k$，有 $\boldsymbol \sigma_k(p^e)={1-p^{k(e+1)}\over 1-p^k}$；其需要先在每个质数处，进行 $O(\log k)$ 的预处理，再进行 $O(n)$ 的转移。 故其复杂度是 $O(\pi(n)\log k)=O(n\cdot {\log k\over \log n})$；只需要保证 $\log k$ 的阶数不超过 $\log n$，则复杂度依然为 $O(n)$。 因此，我们可以说，这个筛法适合于绝大部分的积性函数；甚至我们可以将积性函数定义为一堆函数构成的数列，乘法就是每个位置对应相乘；这样可以同时筛多个积性函数。 当然，上述说明只是表示递推复杂度是 $O(1)$ 且每个质数的预处理复杂度是 $O(\log n)$ 时，筛法复杂度为 $O(n)$，但这并不是筛法的极限。 假设对于质数 $p$ 而言，递推其每个幂次的平均复杂度为增函数 $f(p, n)$，预处理复杂度为增函数 $g(p, n)$，则总复杂度为： $\begin{aligned} T(n)&=&O(n)+\sum_{i=1}^{\pi(n)}g(p_i,n)+\sum_{i=1}^{\pi(n)}\sum_{e=1}^{\lfloor{\log_{p_i}n}\rfloor}f(p_i, n)\\ &=&O(n)+O(\int_1^{{n\over \ln n}} g(x\ln x, n)\text dx)+O(\int_1^{n\over \ln n}f(x\ln x, n)\cdot {\ln n\over \ln(x\ln x)}\text dx) \end{aligned}$ 当然，我的数学水平无法给出这个复杂度达到 $O(n)$ 的条件，但大家可以根据这个公式（或者就基础一点，上面那个求和公式）具体问题具体分析吧...... ~~什么？你看不懂这个公式？那你就感兴理解、别用这个方法，或者直接冲吧。~~