题解 P2158 【[SDOI2008]仪仗队】

JustinRochester · 2018-09-03 14:05:57 · 题解

题目

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) 即满足

当然，我们知道 gcd(0,i)=gcd(i,0)=i

显然，这个式子可以展开为

又因为 y=x 上能被看到的点只有点 (1,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 \Phi(n)=\sum_{i=0}^n\boldsymbol\varphi(i)

所以，式子我们也可以这么写：

终于，我们得到了本题的答案：

那么，这里对于如何求 \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-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^{k_1} p_2^{k_2}-1) 个数中

同理，共 (p_1^{k_1} p_2^{k_2-1}-1) 个数与它最大公因数含 p_2

但是，这里还有这重复枚举

又因为根据性质2，有

因此，带入上式得到性质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} 时

其中，性质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})]

根据 \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。

这就是欧拉函数的性质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

根据前文定义得 \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 的大小

我就是这个地方被卡了好多次......

【代码】

那本蒟蒻就放 我码风极丑的 代码了

新代码：

#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;
}

老代码：

#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程序）

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)

最后安利一下 本蒟蒻的博客

【补充证明】

该证明方法需要对集合、容斥原理、概率有一定的了解

同样地，我们再用容斥原理考虑一下 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 不互质，它们一共有：

提取公因式 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 的方法证明了该式的正确性

（完结撒花）

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

基于此，积性函数可以直接转移：

而我们仅需根据性质2直接递推积性函数在质数幂次的结果即可，代码如下：

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)，则总复杂度为：

当然，我的数学水平无法给出这个复杂度达到 O(n) 的条件，但大家可以根据这个公式（或者就基础一点，上面那个求和公式）具体问题具体分析吧......

什么？你看不懂这个公式？那你就感兴理解、别用这个方法，或者直接冲吧。