P2158 [SDOI2008]仪仗队 [欧拉函数线性筛]

$仪仗队$仪仗队

$Description$Description
点击标题查看链接 .

$正解部分$正解部分
对于一个点 $x,y$x,y, 必须满足 $gcd(x,y)=1$gcd(x,y)=1, 即 $x$x 与 $y$y 互质, 才不被遮蔽,

若不互质, 则其斜率为 $\frac{y}{x}$xy​, 可以约分得到另一个点坐标, 那个点将遮蔽这个点 .

所以题目就转化为: 求有多少点对 $(x,y)$(x,y), 使得 $gcd(x,y)=1$gcd(x,y)=1, 即
$Ans=3+2\ast \sum _{i=2}^{N-1}\sum _{j=1}^{i-1}\left[gcd\right(i,j)==1]=3+2\ast \sum _{i=2}^{N-1}\phi \left(i\right)$Ans=3+2∗i=2∑N−1​j=1∑i−1​[gcd(i,j)==1]=3+2∗i=2∑N−1​φ(i)

(由于按上三角形和下三角形考虑的, 所以要乘 $2$2)

可以使用 欧拉函数线性筛 求出所有 $phi$phi, 最后加起来即可, 时间复杂度 $O\left(N\right)$O(N) .
至于 线性筛 请点击这里 .

#include<cstdio>
#include<algorithm>

const int maxn = 40005;

int phi[maxn], prime[maxn], sign[maxn];
int num;

int main(){
    int N;
        scanf("%d", &N);
        if(N == 1){ printf("0"); return 0; }
        long long Ans = 0;
        for(int i = 2; i < N; i ++){
                if(!sign[i]) prime[++num] = i, phi[i] = i - 1;
                for(int j = 1; i*prime[j] <= N && j <= num; j ++){
                        sign[i*prime[j]] = 1;
                        if(i % prime[j]) phi[i*prime[j]] = phi[i] * phi[prime[j]];
                        else{
                                phi[i*prime[j]] = phi[i] * prime[j];
                                break ;
                        }
                }
                Ans += (long long)phi[i]*2;
        }
        (Ans) += 3;
        printf("%lld", Ans);
    return 0;
}