[BZOJ2190] [SDOI2008] 仪仗队

题目

题目链接,题目大意为一个人站在 n*n 方阵的左下角的点,问他可以看到这个方阵里的多少点。

 

思路

首先考虑什么样的点会被看到,即不被挡住,那什么样的点会被挡住。建立坐标系,如果存在 (i, j),(ik, jk) 这两个点,那么 (ik, jk) 会被 (i, j) 挡住。也就是说每个点的横坐标与纵坐标不可约即横纵坐标互质就不会被挡住。将方阵按逆对角线分开按两个三角形考虑。由于对称,两边可见的点的个数是相同的,所以我们先考虑一边,即考虑 \{(i,j)|i > j\}, 按行考虑,每行不被遮挡的个数为 \sum_{j=1}^{i} (gcd(i,j)==1) 这个恰好就是欧拉函数 \phi(i), 所以一个三角形内的个数即为 \sum_{i=1}^{n} \phi(i), 考虑对角线和边界,最后的答案为1 + 2\sum_{i=1}^{n} \phi(i) 因此,我们只需使用线性筛预处理出欧拉函数即可。
 

代码

 

完结

参考黄学长博客

发表评论

电子邮件地址不会被公开。 必填项已用*标注