首页 > 代码库 > SPOJ_VLATTICE

SPOJ_VLATTICE

2024-07-11 20:00:30   220人阅读

题目是给你一个空间，和一个点(n,n,n)，求从原点出发能够直接接触多少个点（不经过任何一个点）？

典型的mobius反演即可。

首先，ans=3，因为(1,0,0),(0,1,0),(0,0,1)这三个点必看。

其次别在三个平面内反演一次，算出三个坐标轴面的可见点数。

最后在空间反演一次，即可。反演的方法都是分块即可。

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#define maxn 1001000typedef long long ll;using namespace std;int mu[maxn],smu[maxn],pri[maxn];ll n;ll f[maxn],g[maxn];void getprim_mu(){	for (int i=1; i<maxn; i++) mu[i]=1;	for (int i=2; i<maxn; i++)	{		if (pri[i]) continue;		mu[i]=-mu[i];		for (int j=i+i; j<maxn; j+=i) pri[j]=1,mu[j]=-mu[j];		if (maxn/i>=i) for (int j=i*i; j<maxn; j+=i*i) mu[j]=0;	}	for (int i=1; i<maxn; i++) smu[i]=smu[i-1]+mu[i];}ll getnum(ll N){	int next;	ll ans=0;	for (int i=1; i<=N; i=next+1)	{		next=N/(N/i);		ans+=(smu[next]-smu[i-1])*(N/i)*(N/i);	}	return ans;}void _init(){	scanf("%lld",&n);	f[1]=getnum(n);}int gcd(int A,int B) { return B==0?A:gcd(B,A%B); }int main(){	getprim_mu();	int T;	ll ans;	scanf("%d",&T);	while (T--)	{		_init();		ans=3+3*f[1];  		for (int i=1,next; i<=n; i=next+1) 		{			next=n/(n/i);			ans+=(n/i)*(n/i)*(n/i)*(smu[next]-smu[i-1]);		}		printf("%lld\n",ans);	}	return 0;}

　　


联系
我们