【解题报告】luoguP2158 仪仗队

原题链接：https://www.luogu.com.cn/problem/P2158

思路

这道题目经过分析，我们可以发现一个结论

即对于每一个点$(x,y)$，如果能被看到，则一定不存在一个点$(\dfrac x m,\dfrac y m),m, \dfrac x m,\dfrac y m\in Z，$

因为他们属于同一斜率$k= \dfrac y x$

观察可以得到，因为他们没有一个 $m$ 可以使上面的上面的式子成立，即$gcd(x,y)= 1$

然后直接求gcd的话肯定是不行的，然后我们继续看

实际上对于一个固定的 $x$ ，我们要统计的是一个数字 $y\in [1,n]$ 让他们互质，所以我们要求的是x的欧拉函数

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int n,ans;
int ola(int n)
{
	int res=n;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			res-=res/i;
			while(n%i==0)
			n/=i;
		}
	}
	if(n>1)
	res-=res/n;
	return res;
}
int main()
{
	cin>>n;
	if(n==1)
	{
		cout<<0<<'\n';
		return 0;
	}
	for(int i=2;i<=n-1;i++)
	ans+=ola(i);
	cout<<ans*2+3<<'\n';//另一半加上少算的三个 
	return 0; 
}