SPOJ VLATTICE 莫比乌斯反演

题目链接:https://www.spoj.com/problems/VLATTICE/en/

VLATTICE - Visible Lattice Points

Description

Consider a NNN lattice. One corner is at (0,0,0) and the opposite one is at (N,N,N). How many lattice points are visible from corner at (0,0,0) ? A point X is visible from point Y iff no other lattice point lies on the segment joining X and Y.

Input

The first line contains the number of test cases T. The next T lines contain an interger N

Output

Output T lines, one corresponding to each test case.

Sample Input

3
1
2
5

Sample Output

7
19
175

Constraints

T <= 50
1 <= N <= 1000000

Solution

一直想着学一学莫比乌斯反演，一直都没看明白，今天终于学会(套公式)了
之前在洛谷做过一道类似的题(不过那个题是在一个二维平面里),看到这个题就想到了求\(gcd(i,j,k)=1\)的个数，即\[\sum_{i=0}^n\sum_{j=0}^n\sum_{k=0}^n(i,j,k)=1\]
看到gcd(i,j,k)=1,想到迪利克雷卷积的单位元函数好像可以解决,\(\epsilon\big(gcd(i,j,k)\big)\),(\(\epsilon(n)\)为迪利克雷卷积单位元,\(\epsilon(n)=[n=1]\))，接下来我们再用单位元函数和莫比乌斯函数的关系\(\epsilon(n)=\sum_{d|n}\mu(d)\),就可以推出如下计算公式
\[\sum_{i=0}^n\sum_{j=0}^n\sum_{k=0}^n\sum_{d|(i,j,k)}\mu(d)\],
然后我们调整求和顺序，将莫比乌斯函数放到前面，那么可以得到
\[\sum_{d=0}^n\mu(d)\sum_{i=0}^n d\mid i \sum_{j=0}^n d\mid j \sum_{k=0}^n d\mid k\]

SPOJ VLATTICE 莫比乌斯反演

原文：https://www.cnblogs.com/mooleetzi/p/11369402.html