翎驰只能写这种弱智题的题解.
大神请不要点“踩”或回复,并按下 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);
}
}
}