P2158 SDOI2008-仪仗队

前置知识

欧拉定理

题意简析

题目可以简化为求斜率个数（同一斜率上的点只能看到一个）

由 k=y/x 可知 k=y/x=py/px
则已知 互质的 x,y 可以得出一个新的 k
则题意转化为求 gcd(x,y)=1 的个数

此处有几个坑点：

1. 观察者所处未知为（0，0）则边界应为 n-1
2. 边界还有两个斜率未被纳入计算
3. k=1 的斜率被重复计算，需要被减去 1

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
using namespace std;
const long long maxn=16+7;
long long f[maxn];//f[i]指 ψ(i)
long long p[maxn],cnt;//p[i]用于存储第i格质数,cnt用于统计素数个数
long long tag[maxn];//tag[i] 用于记录i是否是素数
long long euler(long long n)//欧拉函数
{
	long long ans=n;
	for(long long i=2; i*i<=n; ++i)
		if(n%i==0)
		{
			ans=ans-ans/i;
			while(n%i==0)  n/=i;
		}
	if(n>1)  ans=ans-ans/n;
	return ans;
}
int main()
{
	long long n;
	cin>>n;
	if(n==1) //n=1 无观察对象
	{
		cout<<0;
		return 0;
	}
	long long Ans=0;
	for(long long i=1; i<=n-1; ++i)
	{
		Ans+=euler(i);
	}
	Ans=Ans*2+1;//Ans*2+2-1
	cout<<Ans;
	return 0;
}