【解题报告】luoguP2158 仪仗队

【解题报告】luoguP2158 仪仗队

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

思路

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

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

因为他们属于同一斜率(k= dfrac y x)

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

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

实际上对于一个固定的 (x) ，我们要统计的是一个数字 (yin [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<<'
';
		return 0;
	}
	for(int i=2;i<=n-1;i++)
	ans+=ola(i);
	cout<<ans*2+3<<'
';//另一半加上少算的三个 
	return 0; 
}