[安师大]sanrd

题解

一、题意

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

二、题解

Step 1 知道一个结论

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

Step 2 推出一个式子

$(0,0)$与$(x,y)$连线，既然干扰的圆都中心对称，那么只需要考虑在连线下方最接近连线的$x$个圆
令干扰圆为$(i,j)$，那么$j=\lfloor\frac{i*y}{x}\rfloor-[i==x]$
由点到直线距离公式（点$(x_0,y_0)$，直线$Ax+By+C=0$）

$$Dis=\frac{|Ax_0+By_0+C|}{\sqrt{A^2+B^2}}$$
得（点$(i,j)$，连线$\frac{y}{x}x-y=0$） $$dis=\frac{|\frac{i*y}{x}-j|}{\sqrt{({\frac{y}{x}})^2+1}}=\frac{|\frac{i*y}{x}-\lfloor\frac{i*y}{x}\rfloor|}{\sqrt{({\frac{y}{x}})^2+1}}$$ $$=\frac{|i*y-\lfloor\frac{i*y}{x}\rfloor x|}{\sqrt{y^2+x^2}}=\frac{i*y\%x}{\sqrt{y^2+x^2}}$$
由于$i$的取值是$1$到$x-1$，$y$与$x$互质（不互质就被$(x/gcd(x,y),y/gcd(x,y))$挡住了）所以$i*y\%x$可以取$[1,x-1]$，$i$为$1$时取$x$，所以连线下方的圆到达连线的最近距离是 $$mindis=\frac{1}{\sqrt{x^2+y^2}}$$
只要$mindis>R/10^6$就可以把$(x,y)$这个圆计算到答案中去$(1km=10^6mm)$
所以需要求的式子就是
$$Ans=\sum_{x=1}^{N-1}\sum_{y=1}^{N-1}[\frac{1}{\sqrt{x^2+y^2}}>\frac{R}{10^6}\&\&gcd(x,y)==1]+2$$
记得最后要加上坐标轴上的两个圆
令$m=\frac{10^{12}}{R^2}$就有
$$x^2+y^2< m$$
$$Ans=\sum_{x=1}^{min(N-1,\sqrt{m})}\sum_{y=1}^{min(N-1,\sqrt{m-x^2})}[gcd(x,y)==1]+2$$

Step 3 Mobius反演

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

$$Ans-2=\sum_{d=1}^{min(N-1,\sqrt{m})}\mu(d)\sum_{x=1}^{min(\frac{N-1}{d},\sqrt{\frac{m}{d^2}})}\sum_{y=1}^{min(\frac{N-1}{d},{\sqrt{\frac{m}{d^2}-x^2}})}1$$
实际上就是用$x$代替了$d*x$
$d$在一定范围内，$\frac{N-1}{d}$和$\frac{m}{d^2}$的值是一定的
这是可以分块做的（Code）
然后也可以用$map$（Code）

感谢：YMDragon，SYC

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
int read()
{
    char ch=getchar();
    int h=0;
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
    return h;
}
const int MAXN=1e6;
int mu[MAXN+1],pri[MAXN>>2],tot;
bool ispri[MAXN+1];
void Mobius()
{
    mu[1]=1;ispri[1]=1;
    for(int i=2;i<=MAXN;i++)
    {
        if(!ispri[i]){pri[++tot]=i;mu[i]=-1;}
        for(int j=1;j<=tot&&i*pri[j]<=MAXN;j++)
        {
            ispri[i*pri[j]]=1;
            if(i%pri[j])mu[i*pri[j]]=-mu[i];
            else break;
        }
    }
}
map<pair<ll,int>,ll>M;
ll Calc(ll m,int n)
{
    if(M.find(make_pair(m,n))!=M.end())return M[make_pair(m,n)];
    ll ans=0;
    for(int i=1;1LL*i*i<=m&&i<=n;i++)
        ans+=min(n,int(sqrt(m-1LL*i*i)));
    M[make_pair(m,n)]=ans;return ans;
}
int main()
{
    Mobius();
    int N=read()-1,R=read();
    ll m=((ll)1e12-1)/R/R,ans=0;
    for(int i=1;1LL*i*i<=m;i++)
        ans+=mu[i]*Calc(m/i/i,N/i);
    printf("%lld\n",ans+2);
    return 0;
}