本文共 2147 字，大约阅读时间需要 7 分钟。

题目描述

广场上的小朋友们排成了整齐的方阵。具体来说，我们可以把每个小朋友看做是一个点，那么小朋友们就形成了 $n\times n$ 的点阵。方阵中，小朋友$A$和小朋友 $B$ 互相可以看见，当且仅当二人之间的连线不经过别的小朋友，且他们之间的距离不超过 $k$ （因为太远就看不见了）。我们想知道有多少对小朋友互相可以看见。$(A,B)$ 与 $(B,A)$ 算同一对。

例如$n=2,k=2$时答案为$6$（距离为$1$的有$4$对，距离为$\sqrt{2}$的有$2$对）

现在我们想要知道，当$n=1000,k=500$时的答案是多少。由于答案过大，请回答对$10^9+7$取模后的结果。

分析

如图所示，显然如果两个点之间会有交点，那么$△ABC$和$△AEF$会构成相似三角形，和第一个例子类似，那么就出现$gcd(|BC|,|AC|)>1$

然后就是找解的过程，如果我们通过每个坐标去枚举周围合法的点，这样的计算量很大，不妨找一下规律：每个点寻找其他点配对时合法方向只有八个，而且上下左右四个方向都是固定的，不难发现就是当$a=0$或$b=0$时，特判这种情况，先对行考虑再对列考虑，这样的数量为$2\ast n\ast (n-1)$

然后我们规定每个点只能向右和向下和其他点配对，因为其他两个方向的和其他点配对会重复，然后第一个点只能分别和下一行以及的第$i+1、j+1$个点配对，第二个点只能分别和下一行以及的第$i+2、j+2$个点配对…这样总的来说就是$2\ast (n-i)\ast (n-j)$

#include 
   
    #include