Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

03/22
14:29
学习笔记 数论

数论学习笔记

好久之前的草稿了QAQ

放出来吧,还没写完,先挖个坑吧放着吧 (虽然不知道还填不填的完)

一、筛法

先从最基本的筛法开始吧

1. 埃式筛

时间复杂度 O(nloglogn)

2. 线性筛

时间复杂度 O(n) 可以用来筛积性函数

每个合数只会被它最小的质因数筛去,保证了时间复杂度

二、一些积性函数

对于一个定义域为{N^ + }的函数f,如果对于任意两个互质的正整数ab,都满足f(ab) = f(a)f(b),则称函数f为积性函数。如果对于任意两个正整数ab 都满足f(ab) = f(a)f(b)的话,则称函数f为完全积性函数。

1.欧拉函数

\varphi \left( n \right) 表示1…n中于n互质的数的个数,这是一个积性函数,具体证明涉及中国剩余定理。

\varphi 函数的取值:

对于一个素数p,自然想到\varphi \left( p \right) = p - 1

对于一个素数pk次方,\varphi \left( {{p^k}} \right) = {p^k} - {p^{k - 1}},也很好证明:

1...{p^k} 中,与 {p^k} 不互质的有 1*p,2*p,3*p ... {p^{k - 1}}*p{p^{k-1}} 个,所以于 {p^k} 互质的数共有 {p^k} - {p^{k - 1}}

对于一个合数n必定能拆成多个质数的乘积的形式,所以\varphi \left( n \right) = n\Pi \left( {1 - \frac{1}{{{p_i}}}} \right)。证明:

\varphi \left( n \right) = \varphi (\Pi p_i^{{a_i}}) = \Pi \varphi \left( {p_i^{{a_i}}} \right)

之前证明得到\varphi \left( {{p^k}} \right) = {p^k} - {p^{k - 1}},变形得到\varphi \left( {{p^k}} \right) = {p^k}\left( {1 - \frac{1}{p}} \right),所以\varphi \left( n \right) = \Pi p_i^{{a_i}}\left( {1 - \frac{1}{{{p_i}}}} \right) = n\Pi \left( {1 - \frac{1}{{{p_i}}}} \right).

线性筛筛欧拉函数时

对于一个合数n有两种情况:

1.n = p * {\rm{i}},且Gcd(p,i) = 1,根据积性函数的性质\varphi \left( n \right) = \varphi \left( p \right)\varphi \left( {\rm{i}} \right)

2.n = p * {\rm{i}},且素数p是i的一个因数,\varphi \left( n \right) = p * {\rm{i}}\Pi \left( {1 - \frac{1}{{Pi}}} \right) = p\varphi \left( {\rm{i}} \right)

2.莫比乌斯函数

  • \mu(n)=\begin{cases}&1 & \text{ if $n$ = 1}\\&(-1)^k & \text{else if $n={p_1}{p_2}{p_3}...{p_k}$}\\&0 & \text{else}\end{cases}

  • {\Sigma _{\left. d \right|n}}\mu \left( d \right) = \left[ {n = 1} \right]

所以用线性筛筛莫比乌斯函数的时候:

对于一个素数p,明显\mu \left( p \right) = - 1

对于一个合数n = p * {\rm{i}},且pi的一个因数,可以想到\left. {{p^2}} \right|n,所以\mu \left( n \right) = 0

对于一个合数n = p * {\rm{i}},且p不是i的一个因数,所以n的质因数的个数比i多1,\mu \left( n \right) = -\mu\left( {\rm{i}} \right)