[关闭]
@xzyxzy 2018-01-22T08:48:33.000000Z 字数 2316 阅读 536

[安师大]sanrd

题解

一、题意

的网格中每个小格为,标号为每个小格(除)中有一个以其中心为圆心,半径为的圆,给你求从方格的中心点能够看到的圆的个数。(一个圆能被看到,当且仅当圆周上存在一个点能被看到;某个点能被看到,当且仅当点与这个点的连线之间,和其他圆没有交点)

二、题解

Step 1 知道一个结论

一个圆能被看到,当且仅当与该圆的圆心的连线与其他圆没有交点
可以产生干扰的圆一定关于连线的中点中心对称,所以对于该圆的圆周上一点,和与关于连线轴对称的,当不断增大时,必然同时不被看见,最后剩下的那个点就是连线与圆周的交点,即得证。

Step 2 推出一个式子

连线,既然干扰的圆都中心对称,那么只需要考虑在连线下方最接近连线的个圆
令干扰圆为,那么
点到直线距离公式(点,直线


得(点,连线

由于的取值是互质(不互质就被挡住了)所以可以取时取,所以连线下方的圆到达连线的最近距离是

只要就可以把这个圆计算到答案中去
所以需要求的式子就是

记得最后要加上坐标轴上的两个圆
就有

Step 3 Mobius反演

将上式进行反演后可以得到


实际上就是用代替了
在一定范围内,的值是一定的
这是可以分块做的(Code
然后也可以用Code

感谢:YMDragon,SYC

Code

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<map>
  7. #define ll long long
  8. using namespace std;
  9. int read()
  10. {
  11. char ch=getchar();
  12. int h=0;
  13. while(ch>'9'||ch<'0')ch=getchar();
  14. while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
  15. return h;
  16. }
  17. const int MAXN=1e6;
  18. int mu[MAXN+1],pri[MAXN>>2],tot;
  19. bool ispri[MAXN+1];
  20. void Mobius()
  21. {
  22. mu[1]=1;ispri[1]=1;
  23. for(int i=2;i<=MAXN;i++)
  24. {
  25. if(!ispri[i]){pri[++tot]=i;mu[i]=-1;}
  26. for(int j=1;j<=tot&&i*pri[j]<=MAXN;j++)
  27. {
  28. ispri[i*pri[j]]=1;
  29. if(i%pri[j])mu[i*pri[j]]=-mu[i];
  30. else break;
  31. }
  32. }
  33. }
  34. map<pair<ll,int>,ll>M;
  35. ll Calc(ll m,int n)
  36. {
  37. if(M.find(make_pair(m,n))!=M.end())return M[make_pair(m,n)];
  38. ll ans=0;
  39. for(int i=1;1LL*i*i<=m&&i<=n;i++)
  40. ans+=min(n,int(sqrt(m-1LL*i*i)));
  41. M[make_pair(m,n)]=ans;return ans;
  42. }
  43. int main()
  44. {
  45. Mobius();
  46. int N=read()-1,R=read();
  47. ll m=((ll)1e12-1)/R/R,ans=0;
  48. for(int i=1;1LL*i*i<=m;i++)
  49. ans+=mu[i]*Calc(m/i/i,N/i);
  50. printf("%lld\n",ans+2);
  51. return 0;
  52. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注