[题解]SP7001 Visible Lattice Points 莫比乌斯反演+数论分块

题目链接
一个点可看见就是它和原点连线没有其他点存在。
我们把所有的有序三元组 ( x , y , z ) (x,y,z) (x,y,z)找出来，发现其中 g c d ( x , y , z ) gcd(x,y,z) gcd(x,y,z)相等的有多个，然而只能取一个。
设 f ( n ) f(n) f(n)为 gcd ⁡ ( x , y , z ) = n \gcd(x,y,z)=n gcd(x,y,z)=n的有序三元组个数，
g ( n ) g(n) g(n)为 gcd ⁡ ( x , y , z ) = n 的 倍 数 \gcd(x,y,z)=n的倍数 gcd(x,y,z)=n的倍数的有序三元组个数，
那么有 g ( n ) = ∑ n ∣ d f ( d ) = ⌊ N n ⌋ 3 g(n) = \sum_{n|d}f(d)={\left \lfloor \dfrac{N}{n}\right \rfloor }^3 g(n)=n∣d∑​f(d)=⌊nN​⌋3
所以 f ( n ) = ∑ n ∣ d μ ( d ) g ( d n ) \begin{aligned} f(n) &= \sum_{n|d}\mu(d)g\left(\dfrac{d}{n}\right)\\ \end{aligned} f(n)​=n∣d∑​μ(d)g(nd​)​
我们求 f ( 1 ) f(1) f(1),故
f ( 1 ) = ∑ d = 1 N μ ( d ) g ( d ) = ∑ d = 1 N μ ( d ) ⌊ N d ⌋ 3 \begin{aligned} f(1) &= \sum_{d=1}^{N}\mu(d)g(d)\\ &=\sum_{d=1}^{N}\mu(d){\left \lfloor \dfrac{N}{d}\right \rfloor }^3 \end{aligned} f(1)​=d=1∑N​μ(d)g(d)=d=1∑N​μ(d)⌊dN​⌋3​
这里还要加上坐标轴上的三个点以及坐标平面上的点。
坐标平面上的点即为三维退化到二维，所以公式为
∑ d = 1 N μ ( d ) ⌊ N d ⌋ 2 \sum_{d=1}^{N}\mu(d){\left \lfloor \dfrac{N}{d}\right \rfloor }^2 d=1∑N​μ(d)⌊dN​⌋2
令
s ( N d ) = ⌊ N d ⌋ 3 + ⌊ N d ⌋ 2 s\left(\dfrac{N}{d}\right)={\left \lfloor \dfrac{N}{d}\right \rfloor }^3 +{\left \lfloor \dfrac{N}{d}\right \rfloor }^2 s(dN​)=⌊dN​⌋3+⌊dN​⌋2
则
a n s = ∑ d = 1 N μ ( d ) s ( N d ) + 3 ans = \sum_{d=1}^{N}\mu(d)s\left(\dfrac{N}{d}\right)+3 ans=d=1∑N​μ(d)s(dN​)+3
数论分块解决，时间复杂度 O ( n + T n ) O(n+T\sqrt{n}) O(n+Tn ​)

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
using namespace std;

const double eps = 1e-10;
const double pi = acos(-1.0);
const int maxn = 1e6 + 10;

int t;
ll p[maxn],mu[maxn];
int cnt;
bool isp[maxn];

void getp(){
	isp[1] = mu[1] = 1;
	for(int i = 2; i < maxn; i++){
		if(!isp[i]) p[++cnt] = i,mu[i] = -1;
		for(int j = 1; j <= cnt && i*p[j] < maxn; j++){
			isp[i*p[j]] = 1;
			if(i%p[j]) mu[i*p[j]] = -mu[i];
			else break;
		}
	}
	for(int i = 1; i < maxn; i++) mu[i] = mu[i-1] + mu[i];
}

inline ll s(ll a){
	return a*a*(a+3);
}

void solve(){
	getp();
	scanf("%d",&t);
	while(t--){
		ll n;
		scanf("%lld",&n);
		ll l = 1, r = 0;
		ll ans = 3;
		while(l <= n){
			r = n/(n/l);
			ans += s(n/l)*(mu[r]-mu[l-1]);
			l = r+1;
		}
		printf("%lld\n",ans);
	}
}

int main()
{
	solve();
	return 0;
}