标题效果：有一个格子组件图，假设三个人在一条直线上，那么第一个人将不会看到第三人。现在，有一个人站在(1,1)在。我问他是否能看到n*n的人数的矩阵。

思考：如果你想站(1,1)这名男子看到了一个立场(x,y)一个人。gcd(x,y) == 1，这是一个经典的模型，仅仅要求出n以内phi的和就能够了。

方法就是线性筛。

CODE：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define MAX 40010

using namespace std;

int n;

bool not_prime[MAX];

int prime[MAX],primes;

int phi[MAX];

void Eratosthenes();

int main()

{

	cin >> n;

	n--;

	Eratosthenes();

	int ans = 0;

	for(int i = 2;i <= n; ++i)

		ans += phi[i];

	cout << (ans << 1) + 3 << endl;

	return 0;

}

void Eratosthenes()

{

	phi[1] = 1;

	for(int i = 2;i <= n; ++i) {

		if(!not_prime[i])

			prime[++primes] = i,phi[i] = i - 1;

		for(int j = 1;j <= primes && prime[j] * i <= n; ++j) {

			not_prime[prime[j] * i] = true;

			if(i % prime[j] == 0) {

				phi[i * prime[j]] = phi[i] * prime[j];

				break;

			}

			else	phi[i * prime[j]] = phi[i] * (prime[j] - 1);

		}

	}

}