题解 UVA11014 【Make a Crystal】

2019-08-29 14:42:42


令 $n=N/2$ ,那么题目中的范围就是 $x,y,z\in[-n,n]$ 。

容易得到答案为

$$\left(6\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n[\gcd(i,j,k)=1]\right)+\left(12\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]\right)+6$$

可以理解成三维都不为 $0$ 的加上一维为 $0$ 的再加上两维为 $0$ 的。

第一项莫比乌斯反演得到

$$6\sum_{i=1}^n\mu(i)\left\lfloor\frac{n}{i}\right\rfloor^3$$

第二项莫比乌斯反演得到

$$12\sum_{i=1}^n\mu(i)\left\lfloor\frac{n}{i}\right\rfloor^2$$

线性筛预处理 $\mu$ 的前缀和,然后数论分块计算即可。

广告 代码