Luogu 2158 – 「SDOI 2008」仪仗队

题目链接:Luogu 2158

考虑什么样子的点可以从左下角被看到。如果$(x,y)$能被看到,那么$(kx,ky)$就不能被看到$(k>1)$,很好理解,斜率相同的线上只能看到第一个点,这个点一定是不可约的(如果可约就说明还可以往左下追溯,那么这个点就不可见),所以能看到的点满足$(x,y)$互质。

那么我们只要看对于每一个$x$,有多少个$y$是和$x$互质。我们可以先考虑$y < x$的情况,那么每个$x$的贡献就是$\varphi (x)$,最终乘以2。特殊地,$y = x$上有一点$(2,2)$也满足(定义左下角$x=1,y=1$)。

这道题需要注意的是左下角的点不是从$(0,0)$开始编号的,也就是说$n = 1$的时候是$1 \times 1$的图形,答案为零,需要特判。对于$n \times n$的图形,在求和的时候也是对$[1,n-1]$的欧拉函数求和,这里特别注意列编号和欧拉函数自变量的映射关系(写几项一比就可以看出来了)。

处理欧拉函数的时候使用筛法,这里我采用的是埃氏筛,时间复杂度为$O(n \log n)$。

 

说点什么

avatar
50
  Subscribe  
提醒