spoj7001 Visible Lattice Points 莫比乌斯反演+三维空间互质对数

时间:2022-07-03 23:41:10
/**
题目:Visible Lattice Points
链接:https://vjudge.net/contest/178455#problem/A
题意:一个n*n*n大小的三维空间。一侧为(0,0,0)另一侧为(n,n,n);
问从(0,0,0)出发的经过该范围三维空间内整数点坐标的射线有多少条。 思路:
类比二维的:求1<=x<=n,1<=y<=n; gcd(x,y)=1的对数。因为y/x,所以可以反过来。
三维的:求1<=x,y,z<=n; gcd(x,y,z)=1的对数。 定义:
f(n) 表示gcd(x,y,z)=n的对数。 F(n) 表示n|gcd(x,y,z)的对数。 f(n) = sigma(mu[d/n]*F(d)) (n|d) f(1) = sigma(mu[d]*F(d)) (1|d); F(n) = (x/n)*(y/n)*(z/n); 由于坐标存在0的情况。当x,y,z两个为0时候,就是坐标轴,三个坐标轴贡献为3;
当x,y,z一个为0的时候,有三个面。为二维的。每一面求一下二维的互质对数[1,n]中gcd(x,y)=1的对数。 ans = 三维对数+3个二维对数+三个坐标轴。 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int, int> P;
const LL INF = 1e10;
const int mod = 1e9 + ;
const int maxn = 1e6 + ;
int prime[maxn], tot, not_prime[maxn];
int mu[maxn], sum[maxn];
void init()
{
mu[] = ;
tot = ;
for(int i = ; i < maxn; i++){
if(!not_prime[i]){
prime[++tot] = i;
mu[i] = -;
}
for(int j = ; prime[j]*i<maxn; j++){
not_prime[prime[j]*i] = ;
if(i%prime[j]==){
mu[prime[j]*i] = ;
break;
}
mu[prime[j]*i] = -mu[i];
}
}
for(int i = ; i < maxn; i++) sum[i] = sum[i-]+mu[i];
}
LL solve2(int n)///x在[1,n],y在[1,n]。求gcd(x,y)=1的对数.
{
LL ans = ;
int last;
for(int i = ; i <= n; i=last+){
last = n/(n/i);
ans += (LL)(sum[last]-sum[i-])*(n/i)*(n/i);
}
return ans;
}
LL solve(int n)///x在[1,n], y在[1,n],z在[1,n] gcd(x,y,z)=1的对数。
{
LL ans = ;
int last;
for(int i = ; i <= n; i=last+){
last = n/(n/i);
ans += (LL)(sum[last]-sum[i-])*(n/i)*(n/i)*(n/i);
}
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
int T;
int n;
init();
cin>>T;
while(T--)
{
scanf("%d",&n);
printf("%lld\n",solve(n)++*solve2(n));
}
return ;
}