翎驰只能写这种弱智题的题解.

大神请不要点“踩”或回复，并按下 Ctrl+W.

有《算法竞赛入门经典》的同志请翻到 322 页例题 10-7，并忽略某翎瞎 BB 的内容.

题图

题图为 $n==6$ 时的情况：

左下角的 3 个可以排除（黄色），另外由于对称，只需考虑一半并乘以 2. 因此我们只考虑下图未被遮挡部分：

一旦能看到点 $(a, b)$，这个点会遮挡住所有 $(ka, kb), k \in Z$.（例如，点 $(2, 1)$ 挡住点 $(4, 2)$）换言之，只要某个点能写成 $(ka, kb), k \in Z$，即 横纵坐标最大公因数不为 1，它就被遮挡了.

欧拉函数

欧拉函数 $\phi(n)$ 是不大于正整数 $n$ 并和 $n$ 互质的正数的个数，或曰区间 $[1, n]$ 内和 n 最大公因数为 1 的整数的个数. Euler's totient function counts the positive integers up to a given integer n that are relatively prime to $n$. It is written using the Greek letter phi as $\phi(n)$. It can be defined more formally as the number of integers $k$ in the range $1 \le k \le n$ for which the greatest common divisor gcd$(n, k)$ is equal to 1. （摘自 Euler's totient function）

亦即，$\phi(n)$ 是第 $n$ 行未被遮挡的点的个数，$\phi (1)==1$.

我们得到：$ans == 3+2\times\sum\limits_{i==2}^{n-1}\phi(a_i)$.

欧拉函数表可以利用类似筛质数的方式得到.

如果你像某翎一样不知道如何筛，请继续阅读.

计算函数表

欧拉函数是积性函数，即 gcd$(a, b)==1 \Leftrightarrow \phi (ab) == \phi (a)\times\phi(b)$. 证明不贴了.

且根据定义有：

$a$ 为质数 $\Leftrightarrow$ $\phi(a)==a-1$.

//phi：函数表；p：质数表；m：最后一个被搜的因数
void table(){
  phi[1] = 1;
  for(int i=2; i<N; i++){
    if(!m[i]) //i 为质数，加入质数表
      p[pt++]=m[i]=i, phi[i] = i - 1;
      for(int j=0; j<pt && p[j] * i < N; j++){
// 遍历所有已查明的质数
        m[k]=p[j];
        if(m[i]==p[j]){
          phi[k]=phi[i]*m[i];
          break;    
        }
        else phi[k]=phi[i]*(p[j]-1);
      }
  }
}