首先我们先把题目分析一下。
emmmm，这应该是一个找规律，应该可以打表，然后我们再分析一下图片，发现如果这个点可以被看到，那它的横坐标和纵坐标应该互质，而互质的条件就是它的横坐标和纵坐标的最大公约数为一，那这题的意思就变成了，在一个n * n的方格内寻找所有点的横坐标和纵坐标互质的点的个数。
但是这样复杂度肯定是过不去的。打表时间花费也是很多的，所以我们需要找到加快速度的方法，就是用欧拉函数来加快速度，所以我们就要实现大的优化，我们先明确欧拉函数是个什么东西.
欧拉函数
\(φ（x）\)表示在\(1\)到\(x - 1\)中所有与x互质的数的个数。这个函数一般就叫做欧拉函数。这个函数还具有一些性质.
- 如果\(x\)是质数，那\(φ（x）=x-1\)。（质数的性质就是这样）
- 若\(m\)与\(n\)互质，那\(φ（n * m）= φ（n）* φ（m）\).（可以根据乘法原理推出）
- 当\(x\)是质数时，那\(φ （x^k）=（x-1）×x^{k-1}\)
所以我们可以通过观察和推算发现，如果想求出结果，那就是对于图的每个横坐标，都记录他的欧拉函数的值，然后加起来就是最终结果。然后把结果乘2，因为纵坐标也需要进行一波这样的操作。最后再加上一（因为2,2这个点也算）
那到底应该怎么筛使得欧拉函数能够很快的算出来呢。
线性筛和欧拉筛
这里我们就要引进两个算法——线性筛和欧拉筛。
线性筛是指以线性的时间筛素数，欧拉筛是以线性的时间求出欧拉函数。
而且他们之间有着异曲同工之妙。
线性筛
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100010
int prime[maxn];//表示第几个质数。
bool vis[maxn] = {0, 1};//判断是否为质数，如果是则为0
int tot;
int main()
{
int n, m;
scanf("%d", &n);
for (int i = 2; i <= n; i++)
{
if (!vis[i])
prime[++tot] = i;
for (int j = 1; j <= tot, prime[j] * i <= n; j++)
{
vis[i * prime[j]] = 1;
if (!(i % prime[j]))//如果i能被prime[j]整除的话
break;
}
}
}
我们分析上面的代码，唯一可能难理解的地方就是\(break\)的那个判断了。这也是欧拉筛的精髓所在，如果已经超出了范围需要退出，这个自不必多说，但是，如果\(i\%prime[j]==0\)时，为啥就要退出呢
原理：
首先我们需要明白一些性质：
我们筛素数时应该从小到大筛，方便后面优化时间，所以源代码循环中\(i\)是从小到大筛的。
任何一个合数都可以表示为几个质数的乘积。所以我们想要在线性时间内筛素数的话，每个合数应该都只被它的最小质因子筛去。
-
当\(i\%prime[j]==0\)时，则\(i\)为\(prime[j]\)的倍数，设\(i\)为\(prime[j]*k\),如果继续向下筛的话，下一个要筛的数是\(i*prime[j+1]=prime[j]*k*prime[j+1]\);此时要筛的数即\(i*prime[j+1]\)就已经被\(prime[j]\)筛去了，而根据性质1，\(prime[j]\)要比\(i\)小（因为\(i\)是\(prime[tot]\)）。
因此时间复杂度是线性的。
欧拉筛
欧拉筛其实跟线性筛差不了多少。
首先我们应该熟记欧拉函数的性质。并且这种筛法还可以进行线性求积性函数。
原理
- 我们看线性筛的第二个性质，欧拉函数是不是也满足，因此防止多余的运算
代码
memset(isprime, 1, sizeof(isprime));
isprime[1] = false;
for (int i = 2; i <= listsize; i++)
{
if (isprime[i])
{
prime[++primesize] =i;
phi[i] = i - 1;//性质1
}
for (int j = 1; j <= primesize && i * prime[j] <= listsize; j++)
{
isprime[i * prime[j]] = false;
if (i % prime[j] == 0)//说明他们之间不互质，且i是prime[j]的倍数，就可以用性质3.
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1)//即phi[j];因为他们互质，所以可用性质1,2
}
}