题意：一个n*n的方阵，从左下角能看到多少个点？
以左下角为原点建立平面直角坐标系，问题等价于，将横纵坐标为小于n的自然数的点与原点相连（不含原点），能连多少条直线。答案等于小于n的互质的数对的个数加上2（x=0，y=0）。
怎样求小于n的互质的数对的个数呢？限制第一个数小于等于第二个数，那么一共有 Σn?1i=1?(i) 个。将其乘2减1即得。
欧拉函数是积性函数。可以用线性筛求积性函数的值。在素数筛的基础上顺带多计算一点东西就好啦。
积性函数求和有更好的方法，还没仔细研究。
一些资料：
【数论】积性函数、莫比乌斯反演、狄利克雷卷积 by NanoApe
浅谈一类积性函数的前缀和 by Tangjz
如何证明莫比乌斯反演？知乎
#include <cstdio>
using namespace std;
const int MAX_N = 40000;
int phi[MAX_N+1], prime[MAX_N+1], ptr;
int main()
{int n, sum = 0;scanf("%d", &n);phi[1] = 1;for (int i = 2; i < n; ++i) {if (!phi[i]) {phi[i] = i-1;prime[ptr++] = i;}for (int j = 0, k; j < ptr; ++j) {if ((k = i * prime[j]) >= n)break;if (i % prime[j] == 0) {phi[k] = phi[i] * prime[j];break;} elsephi[k] = phi[i] * (prime[j]-1);}}for (int i = 1; i < n; ++i)sum += phi[i];printf("%d\n", sum*2+1);return 0;
}