题目链接

题目链接

题意

小朋友们排成了一个n*n的方阵，方阵中，小朋友 AA 和小朋友 BB 互相可以看见，当且仅当二人之间的连线不经过别的小朋友，且他们之间的距离不超过 kk （因为太远就看不见了）。求有多少对小朋友相互看见

思路

• 设（x1，y1）与（x2，y2）相互看见，则gcd(x1-x2,y1-y2)==1
• 找到一对x1-x2和y1-y2，对答案的贡献为 2*(n-x1+x2)*(n-y1+y2)，乘2的原因是两个点坐标差可能一个为正数一个为负数
• 其中有x1-x2=0或者y1-y2=0，对答案的贡献为 2n(n-1)

参考代码

#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;
int main()
{
    int n=1000,k=500;
    long long ans=0;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<n;j++)
        {
            if(__gcd(i,j)==1&&i*i+j*j-k*k<=0)
            {
                ans+=2*(n-i)*(n-j);
                ans=ans%mod;
            }
        }
    }
    ans=(ans+2*n*(n-1))%mod;
    cout<<ans<<endl;
}