首页 > 其他 > 详细

数论函数学习笔记之线性筛

时间:2018-12-12 10:06:49      阅读:171      评论:0      收藏:0      [点我收藏+]

其实主要是想发一下线性筛的板子,包括线性筛质数,欧拉函数和莫比乌斯函数。
当然也会有一点简单的证明。


线性筛质数就不说啦。


然后加一个筛欧拉函数。
\(i\)为质数的时候,自然\(\varphi(i) = i - 1\)
\(n = mp\)
\(m \ \ mod \ \ p == 0\)的时候,有\(\varphi(n) = \varphi(m) * p\)
否则有\(\varphi(n) = \varphi(m) * (p - 1)\)


证明一下吧:
1.若\(m \ \ mod \ \ p == 0\),令\(m = k * p ^ x\),这样保证了\(k, p\)互质。
所以
\(\varphi(n) = \varphi(k) * \varphi(p ^ {x + 1})\)
???\(= \varphi(k) * p ^ x * (p - 1)\)


然后看等式右边:
\(\varphi(m) * p = \varphi(k) * \varphi(p ^ x) * p\)
??????$ = \varphi(k) * p ^ {x - 1} * (p - 1) * p$
??????$ = \varphi(k) * p ^ x * (p - 1)$
(也不知道这算不算证明)


至于\(m \ \ mod \ \ p \neq 0\)时,根据积性,\(\varphi(n) = \varphi(m) * (p - 1)\)


至于筛莫比乌斯函数,就更简单了。
如果\(n\)为质数,则\(\mu(n) = -1\)
\(m \ \ mod \ \ p == 0\),则\(\mu(n) = 0\),
否则\(\mu(n) = - \mu(m)\)

void init()
{
  phi[1] = mu[1] = 1;
  for(int i = 2; i <= n; ++i)
    {
      if(!v[i]) v[i] = i, prime[++prime[0]] = i, phi[i] = i - 1, mu[i] = -1;
      for(int j = 1; i * prime[j] <= n && j <= prime[0]; ++j)
    {
      int k = i * prime[j];
      v[k] = prime[j];
      if(i % prime[j] == 0)
        {
          phi[k] = prime[j] * phi[i];
          mu[k] = 0;
          break;
        }
      else phi[k] = (prime[j] - 1) * phi[i], mu[k] = -mu[i];
    }
    }
}

数论函数学习笔记之线性筛

原文:https://www.cnblogs.com/mrclr/p/10106609.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!