SP7001 VLATTICE - Visible Lattice Points 题解

· · 题解

无需用到莫比乌斯反演，可能是这个题最简单的做法了。

首先设每个点的坐标为 (x,y,z)，再将 \max(x,y,z) 的值相同的点分为一组。
不难发现，这就相当于把题面中给定的正方体拆成很多层。

然后对于每一层进行讨论：

设 (0,0,0) 所在的层为第 0 层。

根据正方体公式可知第 x 层的点数为 (x+1)^3-x^3，化简可得 3x^2+3x+1。

对于点 (x,y,z)，发现其会遮挡 \forall k\in\mathbb{N^*},k\geq2,(kx,ky,kz) 对应点。

所以第 x 层的有效点数为 3x^2+3x+1- 该层所有被遮挡的点的数量。

观察到对于 \forall k\in\mathbb{N^*},k\geq2,(kx,ky,kz) 对应点，它能遮挡的点都会被点 (x,y,z) 遮挡，所以已被遮挡的点对于任何一层无贡献。

可设 dp_i 表示第 i 层未被遮挡的点数，则 dp_i=3i^2+3i+1-\sum_{d|i\wedge d<i}{dp_d}

则对于 (0,0,0) 到 (n,n,n) 的正方体，答案为 \sum_{i=1}^{n}dp_i。 对于 dp 数组的建立，运用类似普通筛的筛法可做到 O(n\log n)，对答案进行前缀和预处理，查询时 O(1) 查询，总时间复杂度为 O(n\log n+T)，空间复杂度为 O(n)，稍劣于莫比乌斯反演写法，但仅仅使用加减乘及位运算，常数更小也更好写。

代码：

#include<stdio.h>
#define int long long
#define N 1000000
int n,ans[N+40];
signed main(){
    for(int i=1;i<=N;++i){
        ans[i]+=3*i*i+3*i+1;//注意是+=而非=，因为ans[i]在这之前可能被修改过
        for(int j=i<<1;j<=N;j+=i)
            ans[j]-=ans[i];
    }
    for(int i=1;i<N;++i)
        ans[i+1]+=ans[i];
    int T;scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        printf("%lld\n",ans[n]);
    }
}

实际上这个做法可以方便的扩展到多维：
对于 x 维空间，起始点坐标都为 0，终点坐标都为 n 的情况下，只需更改第 7 行为 ans[i]+=fpow(i+1,x)-fpow(i,x); 即可，其中 fpow 为快速幂。（当然有时也要取模）