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.

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)，所可以有

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) .

所以：

if(i%prime[j]==0)
{
    phi[i*prime[j]]=prime[j]*phi[i];
    break;
}

\color{red}by \ \ Flwer\_pks