题解 P2158 【[SDOI2008]仪仗队】
傅思维666
·
·
题解
洛谷 P2158 [SDOI2008]仪仗队
洛谷传送门
题目描述
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在，C君希望你告诉他队伍整齐时能看到的学生人数。
输入格式
共一个数N
输出格式
共一个数，即C君应看到的学生人数。
输入输出样例
输入 #1复制
输出 #1复制
说明/提示
【数据规模和约定】
对于 100% 的数据，1 ≤ N ≤ 40000
题解：
一道欧拉函数的经典题。原题是POJ 3090 Visible Lattice Points
来看图说话：
观察这个图，我们首先发现，这个东西是关于直线y=x对称的。接下来我们观察遮挡，根据几何学中的相似知识（三角形相似），我们发现，如果有两个点的横纵坐标构成的两个三角形相似的话，那么那个较大的三角形（那个点）就会被挡住。
什么意思呢？我们发现，一个点可见的条件为：当且仅当(x,y)\in N,x\not=y并且gcd(x,y)=1，即横纵坐标互质。
因为这个图像的大小已知，并且这个图像是关于y=x对称的，那么我们只需要考虑半边的图像有多少点，给它乘二加三（因为有(1,0),(1,1),(0,1)）即可。
不需要双层循环进行枚举，只需要用一层循环枚举y，因为是关于y=x对称的，所以x\in [1,y)，那么，符合条件的x的数量就是y的欧拉函数\Phi (y)。
所以，答案为：
\sum_{i=2}^{n-1}\Phi(i)\times 2+3
为什么是到n-1而不是到n呢？因为原点的坐标是(0,0)，而这个点不能被统计到答案中去（自己不能孤芳自赏），是从0计数的。
然后就简单了，一遍线筛筛选出欧拉函数数组，直接统计答案即可，复杂度是O(n)的。
关于欧拉函数的知识点，如有不太清楚的，敬请移步到本蒟蒻的这篇博客：
博客食用口味更佳
欧拉函数的概念
欧拉函数的定义是：对于一个正整数n，它的欧拉函数是所有小于等于n的正整数中所有与n互质的数的数目。记作\Phi (n)
例：
---
## 欧拉函数的基本性质
欧拉函数的基本性质有三（最基本的）：
$$
\Phi(1)=1
$$
$$
\Phi (p)=p-1 \quad (p为质数)
$$
$$
\Phi(p^m)=(p-1)\times p^{m-1}\quad(p为质数)
$$
第一个很简单我就不说了。
第二个，因为$p$为质数，所以很显然，从$1-(p-1)$的所有数都与其互质，但是因为欧拉函数的定义是**小于等于$p$**的所有数，所以$p$自己是不满足条件的。那么就得证了。
第三个，这是个比较常用的条件。证明也比较好理解，我们可以画一个数轴（在这里我就不画了）。因为$p$是个质数，所以在整个的$p^m$个数中，只有$p$的倍数是与之不互质的，其他的数都与其互质。那么根据**容斥原理**（这个原理只要学完高中数学必修一集合那部分的都应该会），这个$\Phi (p^m)$就应该等于$p^m$减去$p^m$中$p$的所有倍数的个数。因为$p^m=p\times p\times p\cdots p\times p\quad (m个p)$，那么显然，$p$的倍数一共会有$p^{m-1}$个。那么原式可化为：
$$
\Phi(p^m)=p^m-p^{m-1}=(p-1)\times p^{m-1}
$$
---
## 求欧拉函数
根据算术基本定理，任何的一个正整数都可以被唯一分解成若干个质数的积，即：
$$
n=p_1^{m1}p_2^{m2}\cdots p_m^{mm}\quad n\in N_*
$$
我们任取一个数$p$做$n$的质因子，只论$p$的话，那么显然，$p$的倍数都应该被排除掉。同理，如果又有一个$q$也为$n$的质因子，那么$q$的所有倍数也应该被刨除掉。那么还是根据**容斥原理**，$p,q$的公倍数被排除了两遍，所以需要把多排除的那遍加回来。所以就应该是：
$$
n-\frac{n}{p}-\frac{n}{q}+\frac{n}{pq}=n(1-\frac{1}{p}-\frac{1}{q}+\frac{1}{pq})=n(1-\frac{1}{p})(1-\frac{1}{q})
$$
那么，再结合上面的算术基本定理，我们求欧拉函数的通式就应该是：
$$
\Phi(N)=N\times \prod_{质数p|N}(1-\frac{1}{p})
$$
那么，我们显然可以将其在质因数分解的过程中顺便求出来。
代码：
```cpp
int Phi(int n)
{
ans=n;
for(int i=2;i<=sqrt(n);i++)
if(n%i==0)
{
ans=ans/i*(i-1);//这里要是看不明白就在草纸上画一下
while(n%i==0)
n/i;
}
if(n>1)
ans=ans/n*(n-1);
return ans;
}
```
---
## 积性函数及其相关性质
首先放一波积性函数的定义：
如果当$a,b$互质的时候，函数$f(x)$满足$f(ab)=f(a)\times f(b)$，那么$f(x)$就是一个积性函数。
显然欧拉函数是个积性函数（乘法原理）。
积性函数有很多种应用，比如欧拉函数，狄利克雷卷积，莫比乌斯反演等等（滑稽）。但是蒟蒻不会（滑稽）
---
## 线性筛选欧拉函数
当你要求$1-n$的欧拉函数的时候，刚刚的求欧拉函数的方式就比较鸡肋了。所以我们搞出了一个更快的方法——线筛与欧拉函数结合。
其实就是线筛素数，顺便就把欧拉函数也求出来了。
如果有对线筛素数不太熟悉的同学，可以移步这篇博客：
[质数相关知识点详解](https://www.cnblogs.com/fusiwei/p/11354110.html)
代码：
```cpp
void euler(int n)
{
cnt=0;
for(int i=2;i<=n;i++)
{
if(!v[i])
prime[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=n && i*prime[j]<=n;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
```
稍微解释一下这段代码。着重解释一下对$phi[]$数组的处理。
首先，当确定一个数为质数的时候，这个数的欧拉函数就是这个数减一，这个性质在上面有证明。
然后，在线筛模板上，如果$prime[j]$为$i$的一个质因子，那么根据上面的性质，$i\times prime[j]$的所有质因子都已经被$i$包括了。因为欧拉函数是个积性函数，所以else语句后的语句也可以被解释。
---
有了这些知识，就可以得出本题的代码了：
```cpp
#include<cstdio>
using namespace std;
const int maxn=40010;
int phi[maxn],v[maxn],prime[maxn];
int n,cnt,ans;
void euler(int n)
{
cnt=0;
for(int i=2;i<=n;i++)
{
if(!v[i])
prime[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=n && i*prime[j]<=n;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
int main()
{
scanf("%d",&n);
if(n==1)
{
printf("0");
return 0;
}
euler(n);
for(int i=2;i<n;i++)
ans+=phi[i];
printf("%d",ans*2+3);
return 0;
}
```