SP7001 VLATTICE - Visible Lattice Points

莫反入门题

4.SP7001 VLATTICE - Visible Lattice Points

题面翻译

给定一个 $N \times N \times N$ 的立方体，点的编号分别从 $(0,0,0)$ 到 $(N,N,N)$。

求有多少个点从点 $(0,0,0)$ 处能看见或不被遮挡。

题目描述

Consider a N*N*N 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

题目分析

类似于二维平面的等价问题，可以得到除了三个坐标平面内的合法点答案为$\sum\limits_{i=1}^{N}\sum\limits_{k=1}^{N}\sum\limits_{k=1}^{N}[gcd(i,j,k)=1]$记$f(d)$为$\sum\limits_{i=1}^{N}\sum\limits_{k=1}^{N}\sum\limits_{k=1}^{N}[gcd(i,j,k)=d]$,$g(n)$为$\sum\limits_{i=1}^{N}\sum\limits_{k=1}^{N}\sum\limits_{k=1}^{N}[n|gcd(i,j,k)]$易得， $g(n)=(N/n)^3$，且$g(n)=\sum\limits_{n|d}f(d)$。通过倍数形式的莫比乌斯反演，可以得到$f(n)=\sum\limits_{n|d}\mu(d/n)*g(d)$,然后就能得到答案$f(1)=\sum\limits_{d=1}^{N}\mu(d)*(N/d)^3$,同理，二维的点数为$3*\sum\limits_{d=1}^{N}\mu(d)*(N/d)^2$，一维的点数为3，那么就算出来了答案，线性求一下$\mu$就行了。

代码

//
// Created by meiru on 2022/9/22.
//

#include <bits/stdc++.h>

using ll = long long;


int main() {
#ifdef LOCAL
	freopen("in.txt", "r", stdin);
#endif
#ifndef LOCAL
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
#endif
	std::vector<int> prime, vis(1e6 + 10), mu(1e6 + 10);
	mu[1] = 1;
	for (int i = 2; i <= 1e6; ++i) {
		if (!vis[i]) {
			mu[i] = -1;
			prime.push_back(i);
		}
		for (int j = 0; j < prime.size() && i * prime[j] <= 1e6; ++j) {
			vis[i * prime[j]] = 1;
			if (i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				break;
			} else mu[i * prime[j]] = mu[i] * -1;
		}
	}

	int t;
	std::cin >> t;
	while (t--) {
		int n;
		std::cin >> n;
		ll ans = 3;
		for (int d = 1; d <= n; ++d) {
			ll k = n / d;
			ans += mu[d] * (k * k * (k + 3));
		}
		std::cout << ans << '\n';
	}
	return 0;
}