题目描述
广场上的小朋友们排成了整齐的方阵。具体来说,我们可以把每个小朋友看做是一个点,那么小朋友们就形成了n×n 的点阵。方阵中,小朋友 AA 和小朋友BB互相可以看见,当且仅当二人之间的连线不经过别的小朋友,且他们之间的距离不超过 kk (因为太远就看不见了)。我们想知道有多少对小朋友互相可以看见。(A,B) 与 (B,A) 算同一对。
例如, n=2,k=1时答案为 4, n=2,k=2时答案为6(距离为 1 的有 4 对,距离为√2的有2对), n=3,k=2时答案为 2020 。
现在我们想要知道,当 n=1000,k=500时的答案是多少。由于答案过大,请回答对 10^9+7 取模后的结果。
样例
无
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 1e9+7; //题目中的mod;
LL gcd(LL x,LL y)
{
return y ? gcd(y,x%y) : x;
}
int main()
{
LL n = 1000, k = 500, ans = 2*n*(n-1)%N; // ans先计算出方阵边及其以内孩子们可以看到的对数
for(LL x=1; x<n; x++)//枚举一下选取的点,孩子是否可以相互看到
{
for(LL y=1; y<n; y++)
{
if(gcd(x, y) == 1 && x*x+y*y<=k*k) //gcd不为1的话,就表示横着或者竖着肯定被挡住了
{
ans += 2*(n-x)*(n-y), ans %= N;
}
}
}
printf("%lld\n", ans);
return 0;
}
自己的思路(仅供参考)
首先x,y代表两点之间横坐标之差,y表示纵坐标之差,然后用gcd计算是否挡住了.要是挡住了,两个孩子横坐标和纵坐标的差会成倍数关系的,比如第一行选个孩子,第二行孩子肯定可以全看到吧,因为纵坐标只差为1了。gcd(纵横两个差)肯定为1,在看第三行,斜着看,比如本来0,0和1,1两个看得见,现在0,0和2,2,中间1,1,挡住是吧,相当于2,2可以化简为1,1了,这种情况就是gcd(纵横两个差)为1,所以说gcd不为1肯定有人斜着或者横着竖着有人挡住了,斜着方向你可以用数学的相似三角形去看待,反正可以化简成更小的,那肯定有人挡住了;
ans = 2n(n-1)%N; 这一句代码是用来算起初给定方阵边及以内的孩子看得到的对数;
ans += 2(n-x)(n-y), ans %= N; 这一句一方面按照题面计算结果,另外加上方阵内部的孩子可以看到的对数;(可以自己画个图理解一下);