大意

给定一个$n\times n$n×n的点阵，若站在(0,0)这个点问最多能看到多少个点？

思路

30分思路，观察发现，当$gcd(x,y)=1$gcd(x,y)=1时，满足要求，暴力即可，时间复杂度:$O(n^2logn)$O(n2logn)
40分思路，利用公式计算斜率，排序判重，时间复杂度:$O(n^2)$O(n2)
参考代码:

#include<cstdio>
#include<algorithm>
using namespace std;int n,num,m;
double xl[10000001];
signed main()
{
	scanf("%d",&n);if(n==1) return putchar(48)&0;
	if(n==2) return putchar(50)&0;
	for(register int i=1;i<n;i++)
	 for(register int j=1;j<n;j++)
	xl[++num]=i/1.0/j;//计算斜率
	sort(xl+1,xl+1+num);//排序
	m=unique(xl+1,xl+1+num)-xl-1;//去重
	printf("%d",m+2);//输出
}

100分思路，$gcd(x,y)=1$gcd(x,y)=1，假设$x\geq y$x≥y，这种时候就是求$\varphi(x)$φ(x)了，最终答案乘2加1即可，其中暴力求$\varphi(x)$φ(x)复杂度的复杂度为$O(n\sqrt{n})$O(nn​)，线性推复杂度为$O(n)$O(n)

参考图:

代码

#include<cstdio>
#include<algorithm>
using namespace std;long long ans,n;
inline long long phi(long long x)//暴力求phi
{
    long long y=x;
    for(long long i=2;(long long)i*i<=x;i++) if(x%i==0) {y=y/i*(i-1);do x/=i;while(x%i==0);}
    if(x>1) y=y/x*(x-1);
    return y;
}
signed main()
{
	scanf("%lld",&n);if(n==1) return putchar(48)&0;
	if(n==2) return putchar(50)&0;
	for(long long i=1;i<n;i++) ans+=phi(i);//求和
	printf("%lld",(ans<<1)+1);//输出
}