UOJ Logo NaCl的博客

博客

#32. 【SDOI2008】仪仗队

2018-03-15 17:35:43 By NaCl

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

大神请不要点“踩”或回复,并按下 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);
      }
  }
}

评论

poorpool
哇塞你们好强啊qwqqwqqwq我去年这会儿还在学语法QAQQAQ
luv_letters
%%%%%%%%%%%%%
lris
所以说反演有什么用qwq ——(来自线筛都看不懂的鶸)
NaCl
@poorpool @Iris 你们忽略了博文的第 2 行(抖机灵)
NaCl
https://www.luogu.org/paste/c925ro4w

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。