洛谷P2158 欧拉函数

题意：

有一个$n\times n$的方阵，有一个观察者站在$(1,1)$，问他能看到多少个除$(1,1)$外的点

Solution：

视线是个射线，我们考虑经过远点的某条直线$y=kx$，如果存在一个点$(x_0,y_0)$在直线上，那么$2x_0,2y_0$也在直线上，但这是看不到的，于是，对每个斜率$k$，只有满足$\frac{y}{x}=k$且$gcd(x,y)=1$的点才能被看到，斜率值域是$(-\infty ,+\infty )$，于是只需要满足$gcd(x,y)=1$的点都能被$(0,0)$的观察者看到（由于$(0,y),(x,0)$斜率特殊，需要特判）

那么在原题，只需要满足$gcd(x-1,y-1)=1$的点，就可以被看到，其中$x\in [2,n],y\in [2,n]$，即满足$x\in [1,n-1],y\in [1,n-1],gcd(x,y)=1$的点都能被看到，不妨令$x\ge y$，这就是$\varphi (x)$，同理$x\le y$时是$phi(y)$，需要注意的是，当$n\ne 1$时，$(2,2)$点会被计算两次，需要减去一次，当$n=1$时，不存在$(1,2),(2,1)$，不需要+2

答案即

$$(2\sum _{i=1}^{n-1}\varphi (i))-1+2,n>1$$

$$0,n=1$$

// #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=40005,inf=0x3fffffff;
const long long INF=0x3f3f3f3f3f3f,mod=1e9+7;

int n,cnt,prime[N],phi[N];
bool isprime[N];

void make_prime()
{
	memset(isprime,true,sizeof(isprime));
	phi[1]=1; isprime[0]=isprime[1]=false;
	for(int i=2;i<N;i++)
	{
		if(isprime[i])
		{
			prime[++cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt&&i*prime[j]<N;j++)
		{
			isprime[i*prime[j]]=false;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=prime[j]*phi[i];
				break;
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}

int main()
{
	cin>>n;
	make_prime();
	ll ans=0;
	for(int i=1;i<n;i++) ans+=phi[i]<<1;
	cout<<ans+(n!=1);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54