(暴力枚举) $O(n^2)$
预处理出大小为$N$的网格的可见的点的数量,即斜率不同的点的数量
由于网格是对称,所以只需要枚举一半网格即可
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int T,n;
int a[N];
unordered_map<double,int> mp;
int main()
{
a[1] = 3;
for(int i = 2;i<=1000;i++){
int res = 0;
for(int j = 1; j < i;j++)// j为x轴坐标 j < i
{
double t = (double) i / j;
if(!mp.count(t)){
res += 2;
mp[t] = 1;
}
}
a[i] = a[i-1] + res;
}
cin >> T;
for(int i = 1;i<=T;i++){
cin >> n;
printf("%d %d %d\n",i,n,a[n]);
}
return 0;
}