IT狗

【SPOJ7001】Visible Lattice Points-莫比乌斯反演+分块

测试地点:Visible Lattice Points
标题粗心:在三维空间中,咱们说一个点是可见的当且仅当它与点(0,0,0)连成的线段不经由任何其他坐标为整数的点。有T(T50)组扣问,每组扣问给出一个参数N,意为扣问在一切点(x,y,z)(0x,y,zN,1N1106)中,有几多个可见的点,当中x,y,z为整数。分外地,(0,0,0)不算作可见的点。
要领:这一道题是POJ3090的增强版,从二维扩大到了三维,我写的POJ3090题解在此。而这题就不能够简洁地运用欧拉函数的性子来办理成绩了,而须要用莫比乌斯反演来办理。
将点分为三种状况:1.x,y,z均不为0。2.x,y,z中只要一个是0。3.x,y,z中只要一个不是0。关于第一种状况,很简单看出当gcd(x,y,z)=1时,点(x,y,z)是可见的,那末咱们就是请求下面这个式子的值(留意,下文中方括号[]暗示假如括号内的式子为真,值为1,不然值为0):

x=1Ny=1Nz=1N[gcd(x,y,z)=1]

明显暴力图这个式子会炸,这时候咱们就要用到一个莫比乌斯函数的性子:d|nμ(d)=[n=1],这个性子使得咱们可以把上式化成:
Nx=1Ny=1Nz=1d|gcd(x,y,z)μ(d)
阐发第四个乞降号下面的前提,明显d|gcd(x,y,z)的充要前提是d|xd|yd|z,那末上式就可以化成:
Nd=1μ(d)1xNd|x1yNd|y1zNd|z1
这个式子等价于:
Nd=1μ(d)(1xNd|x1)×(1yNd|y1)×(1zNd|z1)
那末这个式子明显即是:
Nd=1μ(d)Nd3
这就是第一种状况的谜底了。第二种状况就是要辨别求gcd(x,y)=1,gcd(y,z)=1,gcd(x,z)=1的点数,式子的推导和下面比较近似,这里就不再赘述了。第三种状况明显只要(0,0,1),(0,1,0),(1,0,0)三个点。这样咱们就找到了一个可以O(N)计较单个扣问谜底的要领。但是O(TN)的总复杂度关于严苛的工夫限定似乎有点拙计,须要想方法优化。留意到Nd的值不会跨越2N种,并且关于同一个Nd的值,知足前提的d是一个陆续的区间,这开导咱们操纵分块头脑优化,成绩变化为怎样求Nd值相称的区间。思索关于恣意一个d,求知足Nd=Np的最大的p。令q=Nd,那末N=dq+r0=pq+r1,咱们明白在q相称的状况下,r1越迫近0p就越大,以是最大的p=Nq=NNd。那末咱们再预处置出μ(i)的前缀和就可以把单个扣问的工夫复杂度加快到O(N),处置扣问的总工夫复杂度为O(TN),可以通过此题。
以下是自己代码:

#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define ll long longusing namespace std;int T;ll N,mu[1000010],sum[1000010];bool prime[1000010]={0};void calc_mu(){  N=1000000;  for(int i=1;i<=N;i++) mu[i]=1;  for(int i=2;i<=N;i++)    if (!prime[i])    {      for(int j=1;i*j<=N;j++)      {        mu[i*j]*=-1;        if (j>1) prime[i*j]=1;        if (!(j%i)) {mu[i*j]=0;continue;}      }    }  sum[0]=0;  for(int i=1;i<=N;i++) sum[i]=sum[i-1]+mu[i];}int main(){  scanf("%d",&T);  calc_mu();  while(T--)  {    scanf("%lld",&N);    ll ans=3,last;    for(ll d=1;d<=N;d=last+1)    {      last=N/(N/d);      ans+=((N/d)+3)*(N/d)*(N/d)*(sum[last]-sum[d-1]);    }    printf("%lld/n",ans);  }  return 0;}

此文由 IT狗 编辑,本网站所发布展示的作品/文章版权归原作者所有,任何商业用途均须联系作者!

相关推荐

评论 暂无评论