初等数论大全

版权所属Wahacer,翻版必究
网站服务器略渣,可能会有卡顿QAQ,暂时没有解决方案,建议下载后看.

离线版pdf点我!!!提取码:qmfv

Contents

数论相关

基础概念

互质

定义

互质:公约数只有1的两个整数,称为互质整数,公约数只有1的两个自然数,叫做互质自然数.举个例子:7 13两个的公约数均为1,所以为互质数.

需要特别注意的是,两个相同的数不是互质数,1与-1与任何数都互质,且他们是唯一的与0互质的整数.

1不为质数

判断互质数的方法

  • 两个不同的指数一定为互质数.
  • 一个质数与另一个不为其整倍数的数为互质数.
  • 相邻的两个自然数为互质数
  • 相邻的两个奇数为互质数.
  • 较大数为质数的两个数为互质数.如103与88
  • 两个数均为合数(两者差较大),较小数所有的质因数,都不是较大数的约数,这两个数为互质数.

如357与715

357=3*7*15

而3、7、17都不是715的约数

这两个数为互质数

  • 两个数均为合数(两者差较小),这两个数的差的所有质因数都不是较小数的约数,这两个数是互质数.

如85和78

85-78=7

7不是78的约数

这两个数为互质数.

  • 两个数均为合数,较大数除以较小数的榆树(大于1)的所有质因数,都不是较小数的约数,这两个数为互质数.

如462与221

462÷221=2……20

20=2*2*5

2、5均不为221的约数

这两个数为互质数.

拓展情况

三个或三个以上自然数互质有两种不同的情况

一种是这些成互质数的自然数是两两互质的.

2、3、5.

另一种不是两两互质的.

6、8、9.


积性函数

定义

若\(gcd(a,b)==1\),如果存在\(f(a*b)=f(a)*f(b)\),则称数论函数\(f\)为积性函数.

这里用数论函数的概念是因为,后文在证明莫比乌斯反演的时候需要用到狄利克雷卷积,适用对象为数论函数,特作声明.

完全积性函数

若\( a,b\in N \),如果存在\(f(a*b)=f(a)*f(b)\),则称数论函数\(f\)为完全积性函数.

性质

  • 若\(f(n)\)是一个非恒等于0的积性函数,则有\(f(1)=1\).
  • 若\(f_1(n)\)和\(f_2(n)\)都是积性函数,则\(f_1(n)*f_2(n)\)也是积性函数.
  • 若\(f_1(n)*f_2(n)\)和\(f_2(n)\)是积性函数,则\(f_1(n)\)也是积性函数。
  • 设\( N=\prod_{i=1}^k{p_i}^{a_i},p\in Pri \),若\(f\)为积性函数,则\( f(N)=f(\prod_{i=1}^k p_i^{a_i})=\prod_{i=1}^kf(p_i^{a_i}) \),如果\(f\)还满足完全积性函数的性质,则\( f(N)=\prod_{i=1}^kf(p_i)^{a_i} \)

剩余系

定义

指对于某一特定的正数\(n\),一个正数集中的数模\(n\)的余数所组成余数域.

完全剩余系

如果存在对于一数\(n\)的剩余系中有\(n\)个余数,则称这个剩余系为完全剩余系.

简化剩余系

对于某一数字\(n\)的剩余系而言,选择其中\(m\)个互质的,然后组成一个新的剩余系,这个剩余系就被称为简化剩余系.


数字分类基础概念

自然数、合数、质数

自然数分为合数和质数(素数),合数是指自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数,与其相对的是质数(因数只有1和它本身)最小的合数是4.

1不是质数也不是合数.

合数又分为完全数和相亲数(相亲数略没意义

完全数

完全数(完美数,完备数)是一些特殊的自然数,他的所有的真因子(即除了本身以外的约数)的和(因子函数),恰好等于其本身.如果一个数恰好等于他的因子之和,则称其为完全数.

如6,他有约数1、2、3、 6,除去其本身,1+2+3=6.

如28,约数为1、2、4、7、14、28,除去28以外,1+2+4+7+14=28.


狄利克雷卷积

定义

设\(f,g\)为两个数论函数.

定义卷积运算\( (f×g)(n)=\sum_{d|n}[f(d)*g(\frac{d}{n})] \)

运算律

  1. 交换律:\( f×g=g×f \)
  2. 结合律:\((f×g)×h=f×(g×h)\)
  3. 存在单位元\( \iota \)使得\( f=\iota×f \)

根据定义.

\( \begin{aligned}(\iota×f)(n)=\sum_{d|n}\iota(d)*f(\frac{n}{d})=f(n)\end{aligned} \)

所以可知.

\( \iota(n)=\begin{cases}1&n=1\\0&n\not=1\end{cases} \)

证明

1.显然

\( \begin{aligned}((f×g)×h)&=\sum_{d|n}(f×g)(d)*h(\frac{n}{d})\\&=\sum_{d|n}\Big(\sum_{q|d}f(q)*g(\frac{d}{q})\Big)*h(\frac{n}{d})\\&=\sum_{d|n,q|d}f(q)*g(\frac{d}{q})*h(\frac{n}{d})\end{aligned} \)

\( \begin{aligned}(f×(g×h))&=\sum_{q|n}f(q)*(g×h)(\frac{n}{q})\\&=\sum_{q|n}\Big(f(q)*\sum_{\frac{d}{q}|\frac{n}{q}}g(\frac{d}{q})*h(\frac{n}{d})\Big)\\&=\sum_{d|n,q|d}f(q)*g(\frac{d}{q})*h(\frac{n}{d})\end{aligned} \)

即相等.

乘法单位元

上面的\(\iota\)是数论函数在卷积意义下的单位元,而普通乘法\( (fg)(n):=f(n)g(n) \)意义下的单位元显然是把所有自然数都映到1的函数,记作\( \varepsilon \).


整除

定义

\( a|b \):若存在整数\(q\)使得非零整数\(a\)与整数\(b\)满足\(b=a*q\),则称为b可以被a整除.

性质

  • \( a|b \) && \( b|c \) , then \( a|c \)
  • \( a|b \) && \( a|c \) , then \( a|( b * x + c * y ) \) , \( a,b,c,x,y\in Z \)
  • \( a|b \) => \( (m*a)|(m*b) \) \( a,b,m\in Z\ \) && \( m\not=0 \)
  • \( a*x+b*y=1 \) \( x,y\in Z \) && \( a|n,b|n \) , then \( (a*b)|n \).

关于第四条性质,需要一些证明如下

n=a*q,n=b*w
nb=a*b*q,na=a*b*w
ab|na,ab|nb
由第二个性质可知
ab|(na*x+nb*y)
ab|n(a*x+b*y)
故当a*x+b*y==1时
ab|n

推论

没证过,证明略

  • 若2能整除\( a \)的最后一位,\( 2|a \)
  • 若4能整除\( a \)的最后两位,\( 4|a \)
  • 若8能整除\( a \)的最后三位,\( 8|a \)
  • 若3能整除\( a \)的各位数字之和,\( 3|a \)
  • 若9能整除\( a \)的各位数字之和,\( 9|a \)
  • 若11能整除\( a \)的(偶数位数字之和)与(奇数位数字之和)之差,\( 11|a \)

同余

定义

给定一个正整数\(m\),如果两个整数\(a\)和\(b\)满足\(a-b\)能够被\(m\)整除,即\((a-b)/m\)得到一个整数,那么就称整数\(a\)与\(b\)对模\(m\)同余,记作\( a\equiv b (mod\ m) \)。

性质

自反性:\( a\equiv a \)\( (mod\ m) \);

对称性:若\( a\equiv b \)\( (mod\ m) \),则\( b\equiv a \)\( (mod\ m) \);

传递性:若\( a\equiv b \)\( (mod\ m) \),\( b\equiv\ c \)\( (mod\ m) \),则\( a\equiv c \)\( (mod\ m) \)

同加性:若\( a\equiv b \)\( (mod\ m) \),则 \( a+c\equiv b+c \)\( (mod\ m) \)

同乘性:若\( a\equiv b (mod\ m) \),则\( a*c\equiv b*c \)\( (mod\ m) \)

    \( a\equiv b (mod\ m) \),\( c\equiv d(mod\ m) \),then \( a*c\equiv b*d(mod\ m) \)

同幂性:\( a\equiv b \)\( (mod\ m) \),then \( an\equiv bn\ (mod\ m) \)

推论

不一定有用

推论1 :\( a*b mod\ k = (a\ mod\ k)*(b\ mod\ k)mod\ k \)

推论2 :\( a\ mod\ p = x \) , \( a\ mod\ q = x \) , \( gcd(p,q)==1 \), 则 \( a\ mod\ p * q = x \)


欧几里得相关

辗转相除

定义

对于两个数,我们需要知道两个数字的最大公因(约)数,可以用欧几里得算法解决,即辗转相除法.我们用\(gcd(a,b)\)表示\(a,b\)的最大公因数.辗转相除的原理是因为\(gcd(a,b)=gcd(x,y-x)\).(可以拓展到多个数,这个自己去看吧……)

证明

令a % b = r, 所以a = k*b+r, 所以r=a-k*b,假设d为a,b的一个公约数,那么 d|a, d|b,所以a-k*b 也一定能被d整除,即 d|r,也就是 d|(a % b), 因此d也是b 和 (a % b)的公约数,因此a,b 的公约数和b, (a%b)的公约数也是一样的,其最大公约数也一定相同,所以gcd(a, b) = gcd(b, a % b)

代码实现

优化

如果需要提高\(GCD\)的效率,可以通过除去里面的因子2来降低常数,总复杂度已经没办法降了……这就是所谓二进制算法,再结合循环优化递归,速度可以很快但谁他妈的会卡这个,毒瘤吧,感兴趣的可以去看看.我没写过


更相损减

类似于辗转相除.(事实上这个除了是减法以外和辗转相除没有任何区别,实现意义是一样的)

代码实现


最小公倍数

定义

对于两个数,我们需要知道两个数字的最小公倍数,也可以用欧几里得算法解决.(我们成最小公倍数为lcm)

\[ lcm(a,b)=\frac{a*b}{gcd(a,b)} \]

这里只说两个数的了,多个数的\(lcm\)自己去看看别的资料吧……

证明

设x=gcd(a,b),y=lcm(a,b)

则a=m*x,b=n*x,m与n互质.

故y=m*n*x.

因此x*y=x*(m*n*x)=(m*x)*(n*x)=a*b

即a*b=gcd(a,b)*lcm(a,b),即lcm(a,b)=a*b/gcd(a,b).

代码实现

优化

这还tm的优化?


扩展欧几里得

定义

扩展欧几里得算法主要用于在已知\(a,b\)的情况下求解一组\(x,y\),使它们满足等式: \(ax+by=gcd(a,b)=d\).

分析等式并证明

  • 当\(gcd(a,b)\)中\(b=0\)时,\(gcd(a,b)=a\),所以一定有\(x=1,y=0\)

  • 当\(b\)不为0时,根据欧几里得定理\(gcd(a,b)=gcd(b,a\ mod\ b)\)可得

    \( ax+by=gcd(a,b)=gcd(b,a\%b)=bx′+(a\%b)y′ \)

  • \( ax+by=bx′+(a\%b)y′=ay′+b(x′−\frac{a}{⌊b⌋}y′ )\)

  • \begin{cases}x=y′\\y=x′−⌊a/b⌋y′\end{cases}

  • 注意第一步,\(gcd(a,b)\)中\(b=0\)时,\(gcd(a,b)=a\),所以一定有\(x=1,y=0\)

  • 所以我们提前开了外挂,知道这个扩欧的最后一个解,可以通过这个解再反推回去

  • 因此只要如代码,从\(gcd(d,0)\)往前处理,在进行欧几里德算法的递归的时候根据相邻两次调用间\(x,y\)和\(x’,y’\)的关系计算即可求出\(ax+by=gcd(a,b)\)的解.

  • 更进一步,对于任意不定式\(ax′+by′=c\),只需要在等式\(ax+by=gcd(a,b)=d\)两边乘上\(\frac{c}{d}\)即可得到解为\(x′=x*\frac{c}{d},y′=y*\frac{c}{d}\)

  • 当然我们可以通过奇技淫巧来得到方程的最小整数解.

如何得到所有解?
实际上在之前的计算和证明中我们得到的只是不定方程的一组解,那么怎样得到所有解呢?对于一般形式ax+by=c有通解x=p+kb,y=q−ka(k为任意整数).(只要代入一下就知道为什么通解是这个了)

代码实现

所以最上面的方程.\( \frac{acx_0}{gcd(a,b)}+\frac{bcy_0}{gcd(a,b)}=c \)也就是任意不等式,可以通过左右同除c的方法把这个变成一般的丢番图方程(裴蜀等式)


求解线性同余方程

裴蜀定理

对任何\( a,b\in Z \)和它们的最大公约数\(d\),关于未知数\(x\)和\(y\)的线性不定方程(称为线性丢番图方程(裴蜀等式)\(ax+by=c\)有整数解\((x,y)\)当且仅当\(d|c\),可知有无穷多解。特别地,一定存在整数\(x,y\),使\(ax+by=d\)成立。

打死我也不证这个,自己yy一下吧.

线性同余方程

对于方程\(ax+by=c\),等价于\( ax\equiv c(mod\ b) \),有整数解的充要条件是前面裴蜀定理说的那些,也就是\(c%gcd(a,b)=0\)

根据这个条件,我们可以通过扩展欧几里得算法求出一组\(x_0,y_0\),也就是\(a*x_0+b*y_0=gcd(a,b\),然后我们两边同时除\(gcd(a,b)\)再乘\(c\),这样可以得到一组方程\( \frac{acx_0}{gcd(a,b)}+\frac{bcy_0}{gcd(a,b)}=c \),这样也就得到一组方程的解.


类欧几里得

类欧几里得


素数相关

素数定义见前文.

素数相关定理

素数有无穷多个.

素数在一定范围的分布并不均匀.看脸

唯一分解定理

定义

若整数\(a\)>=2,那么\(a\)一定可以表示且唯一表示为若干个素数的乘积的形式.即\( a=p_1*p_2*···p_k,p_j\in Prime,1<=j<=k \),我们称\(p_j\)为\(a\)的质因子.
同样,唯一分解定理也可以写成\( a=\prod_{i=1}^kp_i^{m_i} \)

证明

这有什么证明的……

我们可以假设存在自然数不满足这个定理,我们把最小的数字记为\(n\),那么这个数字一定不是一个质数,因为质数\(p\)可以写成\(p=p\),故这个数字只能是一个合数。

所以\(n\)一定可以拆成两个数字的乘积,记为\(a*b\),因为\(n\)已经是最小的不满足定理的数字了,所以\(a,b\)不可能再乘成其他合数的乘积,只能拆成其他质数的乘积,故\(a*b\)也是一样可以拆成多个质数的乘积.

这与假设矛盾,故不存在.

如果\(a,b\)已经是质数了呢?……那\(n\)就已经符合定理了……

代码实现


Pollard_rho

找到一个因子(不一定是质因子),然后再一路分解下去.

该方法基于\(Miller-Rabin\)

流程
  1. 判断是否为质数
  2. 找到当前数\(a\)的一个因子\(d\)
  3. 向下递归该因子\(d\)和除去这个的另一个数\( \frac{a}{d} \).
  4. 循环直到因子为1.

快速找到当前数的一个因子?这就是Pollard_rho的核心之处.随机暴力

寻找因子

对于因子\(p\),定义函数 cal(x) 为\( x\in[0,p),y\in[0,p) \)的随机映射.
常写为\( (x^2+rand())~mod~n \)

初始化\(x=rand(),y=cal(x)\),循环寻找

  1. 令\(p=gcd(|x-y|,n)\),若\(p\not=1\),找到因子直接退出即可。
  2. \(x=cal(x),y=cal(cal(y))\)
  3. \(if(x==y) x=rand(),y=cal(x)\)

就是说当\(x=y\)的时候,一定在一个 \(\rho\) 型循环节上.

大概就长这样.可以形象地理解为两个人在跑步,\(y\)总是在\(x\)前面,\(x==y\)就可以当做是刚好套1圈.

另外通过\(work\)函数来分解素数,如果找到了一个素数因子则加入到因子\(map\)中,否则如果用\(Pr\)找到一个因子则递归去找素数因子。

代码实现


约数个数定理

定义

对于一个数\(n\),可以将其拆分成多个质因子的乘积.

即\( n=\prod_{i=1}^{k}p_i^{a_i} \)

我们可以知道其正约数的个数为\( f(n)=\prod_{i=1}^k(a_i+1) \).

证明

乘法原理.

其余略,实在不知道的可以baidu……


约数和定理

定义

对于一个数\(n\),可以将其拆分成多个质因子的乘积.即\( n=\prod_{i=1}^{k}p_i^{a_i} \)

我们可以知道其正约数的个数为\( f(n)=\prod_{i=1}^k(a_i+1) \).

所以这些所有正约数的和为\( sum=\prod_{i=1}^k(\sum_{j=0}^{a_i}p_i^{j}) \)

证明

乘法原理

其余可以baidu


威尔逊定理

定义

若\(p\)为质数,则 \( (p-1)! \equiv -1(mod\ p)\),\((p-1)!<=>\prod_{i=1}^{p-1}i \),威尔逊定理的逆定理也成立,若某个正整数\(p\)满足\((p-1)!\equiv -1(mod\ p)\),可以判断\(p\)一定是质数
不过似乎没什么用?没见有人这样判定过的.

证明

这真没什么证明的了……硬要证明只能从这个充分性和必要性证明了……感兴趣的去网上看看资料吧……


费马小定理

定义

若\(p\)是素数,\(a\)为正整数,且\(gcd(a,p)==1\),则\( a^{p-1}\equiv 1(mod\ p) \)

证明

首先,\(p-1\)个整数\(a,2a,3a,···,(p-1)a\)中没有一个是\(p\)的倍数.并且他们当中都与\(p\)互质.

所以,\(a,2a,3a,···,(p-1)a\)对模\(p\)的同于既不为0,也没有两个同余相同,因此,这\(p-1\)个数对模\(p\)同余,一定是\(1,2,3,···,p-1\)的某种排列.

即\( a*2a*3a*···*(p-1)a\equiv 1*2*3*···*(p-1)(mod\ p) \)

化简可得.

\( a^{(p-1)}*(p-1)!\equiv (p-1)!(mod\ p) <=>a^{p-1}\equiv 1(mod\ p) \)(这一步化简可以看成威尔逊定理,同余式子中可以左右同除一个与模数互质的数,具体详见上文剩余系.)

也可以看做是\(a\)的逆元乘\(a^p\)与1关于\(p\)同余,因为\(p\)是个质数,所以也可以写成费马小定理的标准形式.

\[ a^p\equiv a(mod\ p) \]

时间复杂度

费马小定理可以用来求逆元,时间复杂度是快速幂的时间复杂度\(log_2n\)


欧拉相关

欧拉定理
定义

费马小定理是描述当模数为素数的时候,指数的同余性质,当模数为合数的时候,就需要欧拉函数.

若\(gcd(a,m)==1\),可得\( a^{\phi(m)}\equiv1(mod~m) \)

证明见后文.

欧拉函数
定义

对正整数\(n\),欧拉函数是小于等于\(n\)的数中与\(n\)互质的数的数目.欧拉函数写作\( \phi \).

性质
  1. 若\(n\)是一个素数,则\(\phi(n)=n-1\)
  2. 若\(n\)是一个素数\(p\)的幂次\( p^a \),则有\( \phi(p^a)=(p-1)*p^{a-1}<=>p^a-p^{a-1}<=>p^a*(1-\frac{1}{p}) \)
  3. 若\(n\)任意两个互质的数\(a,b\)的积,则\( \phi(a*b)=\phi(a)*\phi(b) \)
  4. \( \sum_{d|n}\phi(d)=n \)
  5. 当\(n>1\)时,\(1-n\)中与\(n\)互质的整数和为\(\frac{n\phi(n)}{2}\)
证明

①显然可知.

②可知比\( p^a \)小的正整数有\(p^a-1\)个.其中所有能被\(p\)整除的数都可以表示为\(p\)的倍数(\( p*t(t=1,2,···,p^{a-1}-1) \)).通过整理可以发现一共有\(p^{a-1}-1\)个这样的数能被\(p\)整除,并且这些数并不与\(p^a\)互质,根据定义可知\( \phi(p^a)=p^a-1-(p^{a-1}-1)=(p-1)*p^{a-1} \)

③在比\(a*b\)小的\(a*b-1\)个整数中,只有那些既与\(a\)互质的数(\( \phi(a) \)个)和既与\(b\)互质的数(\( \phi(b) \)个)才会与\(a*b\)互质,所以根据乘法原理一共就有\(\phi(a)*\phi(b)\)个,等价于\(\phi(a*b)\)个.

④\(n\)为1的时候,显然,其余用数学归纳法证明即可,这里就不过多罗列.

推论

设\( n=p_1^{a_1}*p_2^{a_2}*···*p_k^{a_k} \)可得\( \phi(n)=n*(n-\frac{1}{p_1}*\frac{1}{p_2}*···*\frac{1}{p_k})<=>n*\prod_{i=1}^{k}(1-\frac{1}{p_i}) \)

证明

因为\( \phi(n)=\phi(p_1^{a_1}*p_2^{a_2}*···*p_k^{a_k})=\phi(p_1^{a_1})*\phi(p_2^{a_2})*···*\phi(p_n^{a_n})) \)

由上面性质②可知,\( \phi(p^a)=p^a*(1-\frac{1}{p}) \)

所以按照以上方式展开式子既得

\( \phi(n)=\prod_{i=1}^k p^{a_i}-\prod_{i=1}^{k}(1-\frac{1}{p_i}) \),其中\( n=p_1^{a_1}*p_2^{a_2}*···*p_k^{a_k} \)。

所以\(\phi(n)=n*\prod_{i=1}^{k}(1-\frac{1}{p_i})\)


素数判定及测试

可以通过几个方法来判断是不是质数。

  1. 暴力枚举
  2. 威尔逊逆定理
  3. Miller_Rabin素数判定
  4. 某些筛素数方法(同后面线性筛一块讲)

暴力枚举

通过枚举\( 1-\sqrt n \)的所有数字去判断是否是质数.

代码实现

威尔逊逆定理

若某个正整数\(p\)满足\((p-1)!\equiv -1(mod\ p)\),可以判断\(p\)一定是质数.但是需要考虑阶乘,可以通过预处理阶乘,稍快一些,但因无法取模并且很快会爆long long,有很大的局限性.也可以考虑暴力乘计算,但是需要\(O(n)\)的复杂度,(注意,快速乘比直接乘起来模要慢,就是乘起来模可能会爆long long.)

代码实现

不建议使用这种判断方法

Miller_Rabin素数测试

前置技能:费马小定理,快速幂.

费马小定理:若\(p\)是素数,\(a\)为正整数,且\(gcd(a,p)==1\),则\( a^{p-1}\equiv 1(mod\ p) \)

一种基于费马小定理的逆定理的判断素数的方法.首先这个逆定理是错误的.但是只有\(\frac{1}{4}\)的概率算错.所以我们可以通过多次判断来验证素数以提高正确性.

时间复杂度

\[O(log_2n\times cnt)\]

cnt表示判断次数.

代码实现

二次探测

对于\(Miller_Rabin\)算法而言,可以通过二次探测来优化,从而提高正确性,降低时间复杂度.

如果\(p\)是素数,\(x\)是小于\(p\)的正整数,且\(x^2\equiv 1(mod\ p)\),那么\(x=1\ or\ x=p-1\).

证明:因为\(x^2\equiv 1(mod\ p) <=>p|(x^2-1)<=>p|(x+1)(x-1)\)

由于\(p\)是素数,那么只可能是\(x-1\)能被\(p\)整除(此时\(x=1\) 或 \(x+1\)能被\(p\)整除(此时\(x=p-1\)。

不断地提取指数\(n-1\)中的因子2,把\(n-1\)表示成\(d*2^r\)(其中\(d\)是一个奇数)。那么我们需要计算的东西就变成了\( a^{d*2^r} \)除以\(n\)的余数。于是,\( a^{d*2^{r-1}} \)要么等于1,要么等于\(n-1\)。

如果\( a^{d*2^{r-1}}==1 \),定理继续适用于\( a^{d*2^{r-2}} \),这样不断开方开下去,直到对于某个\(i\)满足\( a^{d*2^{r-i}}mod\ n=n-1 \),或者最后指数中的2用完了得到的\( \begin{cases} a^{d}mod\ n=1\ \\a^{d}mod\ n =n-1\end{cases} \)
所以我们得到了某个奇怪的二次探测定理:

如果\(n\)是一个素数,且\(0<x<p\),则方程\(x^2\%p=1\)的解为:\( x=1\ or~x=p-1 \).

这个确实要比一般的暴力探测要快一些,但是我基本没写过啊Orz

代码实现


求解离散对数

BSGS及其拓展


逆元

定义

\(若a*x\equiv 1(mod\ b)\),\(gcd(a,b)==1\),则称\(x\)为\(a\)的逆元,记为\(a^{-1}\).

可以理解为除意义下的模.对于计算\((t/a)\%b\)的时候可以转化为\(t*a^{-1}\%b\)

a和p互质,a才有关于p的逆元

三种求法

费马小定理求逆元

前置技能:素数相关定理:费马小定理

因为一般的模数都是质数,所以我们可以直接套用费马小定理.

\[ a^{m-1}\equiv 1(mod\ m)=>a*a^{m-2}\equiv 1(mod\ m)=>a^{m-2}\equiv \frac{1}{a}(mod\ m) \]

所以逆元就是\(a^{m-2}mod\ m\).直接套用快速幂求.

时间复杂度

\[O(log_2n)\]

代码实现


扩欧求逆元

扩欧最后所求的就是\(a*x + b*y = 1\),如果\(ab\)互质,有解,这个解的\(x\)就是\(a\)关于\(b\)的逆元,\(y\)就是\(b\)关于\(a\)的逆元.

证明

两边同时求余b

\(a*x \% b + b*y \% b = 1 \% b\)

\(a*x \% b = 1 \% b\)

\(a*x = 1 (mod\ b)\)

所以……这个\(x\)不就是逆元么

时间复杂度

\[O(log_2n)\]

代码实现


递推求逆元

我们可以直接通过递推式线性求出逆元.

递推式

\[ inv[i]=-(p/i)*inv[p\%i] \]

证明

设\(inv_i\)为\(i\)的逆元.\(t=p/i\).\(k=p\bmod i\),\(p\)为质数.

\( t*i+k\equiv0\ mod\ p \)

移相可得.\( -ti\equiv k\ mod\ p \)

左右同时除以\(i*k\)可得.

\( -\frac{t}{k}\equiv \frac{1}{i}\ mod\ p <=> -t*inv_k\equiv inv_i\ mod\ p \)

因为同余,所以我们可以加一个而不改变这个式子的值(也就是说可以把这个化成正数形式

\( inv_i\equiv p-t*inv_k\ mod\ p <=> inv_i\equiv (p-p/i)*inv_{p\%i}\ mod\ p \)

\(p\%i\)是比\(i\)小的,所以可以递推求解.

代码实现


中国剩余定理

中国剩余定理


莫比乌斯相关

莫比乌斯函数

定义

\( \mu(n)=\begin{cases}1&n=1\\(-1)^k&n=\prod_{i=1}^kpi\\0&other~cases\end{cases} \)

性质

  • \[ \sum_{d|n}\mu(d)=[n==1] \]

当\(n\)为1时,函数的值是1,其余情况都为0.

  • \( \mu(a*b)=\mu(a)*\mu(b),gcd(a,b)==1 \)

莫比乌斯函数存在互质积性

当\(a,b\)互质的时候,其函数的值都是0……就算有1……乘一下也变成0了……

  • \(\varepsilon\) 在卷积意义下的逆元即为\( \mu \).满足且唯一满足 \(\varepsilon×\mu=\iota\)
  • \(\iota(n)=\sum_{d|n}\mu(d) \)

当\(n==1\),显然成立.

当\( n\not=1=>n=\prod_{i=1}^kp_i^{a_i} \)

\(\begin{aligned}\sum_{d|n}\mu(d)&=\mu(1)+\mu(p_1)+\mu(p_2)+···+\mu(p_ip_2)+···+\mu(p_1p_2···p_k)\\&=\dbinom{k}{0}+\dbinom{k}{1}(-1)+\dbinom{k}{2}(-1)^2+···+\dbinom{k}{k}(-1)^k\\&=(1-1)^k\\&=0\end{aligned}\)

莫比乌斯反演

定义

已知\(f\)为数论函数.\(F\)为数论函数\(f\)的求和函数.

即\( F(n)=\sum_{d|n}f(d) \)

公式

\[ F(n)=\sum_{d|n}f(d)<=>f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d}) \]

证明

反演式子左边可以看做是\(F=f×1\),即前文说到的狄利克雷卷积展开.

分析\(1×f\)

\( \begin{aligned}1×f&=F\\f×(1×\mu)&=F×\mu \\ f×\varepsilon&=F×u\\f&=F×u\end{aligned} \)

即反演.

线性筛

暴力筛

时间复杂度

\[ O(N\sqrt N) \]

换成Miller_Rabin可以把时间复杂度优化到\( Nlog_2N \)

代码实现

埃氏筛(Eratosthenses)

时间复杂度

\[ O(Nlog_2{log_2N}) \]

证明

对每一个 \(p\), 要进行 \(\lfloor\frac{n}{p}\rfloor\) 次运算,全部加起来,就是 \( n*\sum_{i=1}^{\sqrt n}\frac{1}{p} \)

简单讲就是 \(\sum_{i=1}^{n}\frac{1}{p}\) 约等于\(log_2n\) 所以\( \sum_{i=1}^{\sqrt n}\frac{1}{p} \)大概就是\( log_2log_2n \).

代码实现

线性筛

时间复杂度

\[O(n)\]

证明

设合数\(n\)的最小的一个质因数为\(p_1\),另一个比\(p\)大的质因子是\(p_2\),设\(n=p_1*m=p_2*k\),根据程序可以发现,合数\(n\)在筛到\(p_1\)的时候先被筛去,而不会被\(p_2\)再筛一次,所以保证了每一个数字只会被筛一次,所以时间复杂度是\(O(n)\)的.

代码实现

拓展

对于线性筛而言,我们可以有更广的用途.

  • 我们可以根据积性函数的性质从而线性求出莫比乌斯函数、欧拉函数、约数个数函数、约数和函数等积性函数.

从而我们可以发现,对于构造出的一个积性函数,如果可以证明其积性,考虑其最小的质因子在其当中出现的个数,再根据其积性从而线性递推即可.反正考场上也写不出来……

致谢

贾志鹏线性筛

线性筛,积性函数,狄利克雷卷积,常见积性函数的筛法

ACM数论之旅6—数论倒数,又称逆元(我整个人都倒了( ̄﹏ ̄))

其余忘记名字的网上博客…

xqmmcqs

Wahacer


以上.
感谢各位的观看

初等数论大全》有3个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注