P2158 [SDOI2008]仪仗队

嗯，这个题是个数学题，好像没有那么难，~~但我当时就是不会。~~ 首先这个题我们自然会想到要枚举斜率$qwq$. 也就是说对于每个$x/y$，只会为最终答案加一。 那么事实上，我们完全可以通过一次$O(n)$的模拟来枚举每个横坐标，然后套一层$O(n)$的枚举斜率，解释如下。 假设我们队伍看坐在坐标系里面，那么对于每个至少经过一个人的斜率$k$，总可以可以表示为既约分数$$\frac{w_1}{w_2} \quad\ gcd(w_1,w_2)=1$$ 那么事实上也可以表示成如下：$$\frac{w_1*t}{w_2*t} \quad\ (t \in{Z})$$ 两者的$k$完全相同，但是会重复计算，所以我们考虑用$O(n^2)$的时间记录一下并枚举来计算结果。 好像海星，但是太慢了，所以我们考虑这个题的数学本质。 倘若我们只枚举每一个横坐标，与之会对应的有$n$个纵坐标，组成$n$个二元组，那么我们只需要计算出有多少个二元组的横纵坐标互质即可。因为在这里我们选择将有效斜率集合的代表元记为既约分数的形式，所以如果一个点的横纵坐标仍有公因子，就肯定是重复的，所以不去管它。 那么现在很明确了，就是对于每个横坐标，记录它的$\phi$，求和即为有效答案。 但在这个地方有几个小细节： 1、枚举完横坐标之后把结果$\times{2}$，因为纵坐标也需要，枚举。 2、我们要从$2 $ ~ $ n-1$枚举，因为第一列和最后一行的人要特判。 3、最后要加上$3$,其中加$2$是因为位于第一列和最后一行没有计算进去，再加$1$是因为我们枚举$\phi$的时候是不会把$w1=w2$考虑在内的，所以要$+1$ 那么接下来我们考虑如何求$\phi$ 事实上，我们可以通过$n\sqrt{n}$的时间来枚举约数，从而推出每个$\phi$.但是在这里介绍线性推的方法——**欧拉筛**。 实际上，与其说跟素数筛相似，不如说素数筛是借鉴的欧拉筛。对了，这个地方有一个误区，欧拉筛只针对于筛$\phi$。毕竟$\phi$的名字叫做欧拉函数嘛$qwq$. ```cpp int cnt=1,prime[100001],phi[100001]; bool check[100001]; inline void init(int n) { for(int i=2;i<=n;i++ { if(!check[i]) { phi[i]=i-1; prime[cnt++]=i; } for(int j=1;j<=cnt;j++) { if(prime[j]*i>n)break; check[i*prime[j]]=1; if(i%prime[j]==0) { phi[i*prime[j]]=prime[j]*phi[i]; break; } else phi[i*prime[j]]=phi[i]*phi[prime[j]]; } } } ``` 类比线性筛而言，我们可以发现，对于一个素数$p$而言，$\phi(p)=p-1$，那么因为凡是素数必然在合数之前被筛到，所以我们可以考虑以此为基进行欧拉筛。那么，由于若$W=a\times{}{}b$且$gcd(a,b)=1$，就会有$\phi(W)=\phi(a)\times \phi(b)$，所可以有 ```cpp else phi[i*prime[j]]=phi[i]*phi[prime[j]]; ``` 那么对于另一种情况而言，我们考虑有$$w=j^{n} \times {x}$$且其中$gcd(j^n,x)=1$ 那么此时就会有$\phi(w)=\phi(j^n) \times \phi(x)$ 而因为事实上$\phi(j^{n})=j^n-j^{n-1}$ 所以会有$\phi(w)=\phi(x) \times j\times(j^{n-1}-j^{n-2})$ 而这个$\phi(x) \times (j^{n-1}-j^{n-2})$即是我们当前枚举到的$\phi(i)$ . 所以： ```cpp if(i%prime[j]==0) { phi[i*prime[j]]=prime[j]*phi[i]; break; } ``` # $\color{red}by \ \ Flwer\_pks$