最新要闻

广告

手机

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

 宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

家电

  1. 首页
  2. 移动通信
  3. 内容

欧拉函数

来源：博客园

欧拉函数的几个性质（以下 \(p\) 无特殊说明，都为质数）：

  1. 若 \(gcd(a,b)=1\) ，则 \(\varphi(a)\times \varphi(b)\)，证明不会，大家记住就行了

  2. \(n=\sum_{d|n}\varphi(d)\)


    【资料图】

    证明：设 \(f(x)\) 表示 \(gcd(k,n)=x\) 的数的个数（ \(k<=n\) ）

    结论：\(n=\sum_{i=1}^nf(i)\)

    我们可以分类讨论（保证 \(x<=n\)）：

    1. \(x\) 是 \(n\) 的约数，那么 \(gcd(x,n)=x\) ，可以有 \(1\) 的贡献
    2. \(x\) 不是 \(n\) 的约数，\(x\) 也和 \(n\) 不互质，那么一定会被他们俩的最大公约数带来 \(1\) 的贡献
    3. \(x\) 和 \(n\) 互质，那么会被 \(gcd(x,n)=1\) 带来 \(1\) 的贡献

    综上：每个数 \(x\) 都会且只会被统计一次 \(1\) 的贡献

    证出结论：\(n=\sum_{i=1}^nf(i)\)

    现在我们观察上面的式子：\(gcd(k,n)=d\) 等价于 \(gcd(\frac{k}{d},\frac{n}{d})=1\) 也就等价于 \(\varphi(\frac{n}{d})\)

    所以上面的结论可以转化成：\(n=\sum_{d|n}\varphi(\frac{n}{d})=\sum_{d|n}\varphi(d)\)

  3. 若 \(n=p^k\) ，则 \(\varphi(n)=p^k-p^{k-1}\)

    可以看出用到了容斥，用总的数量，减去和 \(n\) 不互质的数量。

    法一：设 \(x\) 为 \(p\) 的系数，则 \(x\) 的取值范围为 \(1,2,3,...,p^{k-1}\) ，所以总共有 \(p^{k-1}\) 个与 \(n\) 不互质的数

    法二：\(p^k/p\) 就是 \(p\) 的倍数在 \(1-n\) 中出现的个数，即 \(p^{k-1}\)

  4. \(\varphi(p^k)=p^{k-1}\times(p-1)\)

    这个证明是简单的

    上面已经得出 \(\varphi(p^k)=p^k-p^{k-1}\) 我们把 \(p^{k-1}\) 提出来

    可以得到 \(\varphi(p^k)=p^{k-1}\times(p-1)\)

  5. \(\varphi(n)=n*\prod_{i=1}^c\frac{p_i-1}{p_i}\) （ \(c\) 是 \(n\) 的质因数个数）

    证明：

    已知 \(n=\prod_{i=1}^c \varphi(p_i^{k_i})\) （证明：由 \(1\) 性质可知）

    则 \(n=\prod_{i=1}^c (p^k-p^{k-1})\) 这次我们提出来 \(p^k\)

    式子就变成 \(n=\prod_{i=1}^c(p^k\times(1-\frac{1}{p}))\)

了解了这些性质以后，我们就可以愉快的进行欧拉筛了

分类讨论：

  1. 若 \(p\) 为素数，则 \(\varphi(p)=p-1\)

  2. 发现 \(n\) 会被 \(p\times n"\) 筛掉

    1. \(p\) 是 \(n"\) 的最小质因数，\(\varphi(n)=p\times \varphi(n")\)

      证明：

      \(\varphi(n)=n\times\prod_{i=1}^c\frac{p_i-1}{p_i}\)

      把 \(n\) 分解成 \(p\times n"\) 可知 \(\varphi(n)=p\times n"\times\prod_{i=1}^c\frac{p_i-1}{p_i}\)

      把后两项合并得： \(\varphi(n)=p\times \varphi(n")\)

    2. \(p\) 不是 \(n"\) 的最小质因数

      则 \(\varphi(n)=\varphi(n")\times p\)

      即 \(\varphi(n)=\varphi(n")\times(p-1)\)

到这里，欧拉筛就结束了，花了一晚上时间，一个题没调，但是感觉理解的透彻多了！

给个代码，大家可以理解一下：

void init(){phi[1]=1;for (int i=2;i

关键词：