h5网站建设方案.doc,seo外包优化网站,小程序拉新项目,网站建设申请计划文章目录前言质数相关质数判断求约数求取区间质数埃氏筛法线性筛法分解质因数欧拉欧拉函数求取单个数线性筛法求取欧拉定理求逆元快速幂/幂取模欧几里得算法求最小公约数拓展欧几里得算法求解同余方程前言
本文主要是提供Python版本的常见的一些与数论相关的模板#xff0c;例…
文章目录前言质数相关质数判断求约数求取区间质数埃氏筛法线性筛法分解质因数欧拉欧拉函数求取单个数线性筛法求取欧拉定理求逆元快速幂/幂取模欧几里得算法求最小公约数拓展欧几里得算法求解同余方程前言
本文主要是提供Python版本的常见的一些与数论相关的模板例如求解质数质因数分解简单博弈论以及组合型问题经典的括号匹配组合问题等等。至于原理与证明的话由于存在大量的数学公式推理因此本文不展示仅展示代码与变量说明和使用场景。
注意 相关原理将使用红色字体进行标注证明可自行查阅资料。本文不再赘述
质数相关
质数判断
朴素方式
def isPrim(n):if(n1):return Falsefor i in range(2,n):if(n%i0);return Falsereturn True之后的话由于除法的一些性质,当 n/d d 的时候d^2 n 在这个循环过程当中 d^2 n 这个时候的话是没有必要全部除去的只需要一般就好了。
优化版本
def isPrime(n):if(n1):return i 2while(i(n//i)):if(n%i0):return Falsereturn True求约数
这个的话就是前面说的那句话的比较好的运用
def yueShu(n):i 1while(in//i):if(n%i0):print(i)if(i!n//i):print(n//i)i1此外
求取区间质数
现在我们知道了如何判断一个质数那么现在我们需要求取一个区间内的质数例如我们需要求取从1~n之间所有的质数有哪些
埃氏筛法
直接看到代码
def getPrims(n):prime [0] * (n1):st [False] * (n1)cnt 0for i in range(2,n1):if(not st[i]):prime[cnt] icnt1j iiwhile(jn):st[j] Trueji
这个的话就是把这个质数的倍数给筛掉。
线性筛法
埃氏筛法的效率还是可以的但是还可以优化一下。
def getPrim(n):prime [0] * (n1):st [False] * (n1)cnt 0for i in range(2,n1):if(not st[i]):prime[cnt] icnt1j 0while(prime[j] n//i):st[prime[j]*i] Trueif(i%(prime[j])0):breakj1这个的话就是把那个筛选的给优化了一下。
分解质因数
ok,接下来是分解质因数这个分解质因数是很有用的东西。
N p1^a1 * p2*a2 …pk^ak 对于一个数N都可以拆解为这样的样子其中这个P是质数
def division(n):i 2while(in/i):if(n%i0):a 0while(n%i0):n//ia1print(当前质因数为{},对于的幂是{}.format(i,a))if(n1):print(当前质因数为{},对于的幂是{}.format(n,1))欧拉
这个东西的话和我们的这个质数还是有点关系的。
欧拉函数
欧拉函数φ(5) 表示从1~5 当中和5 互质的元素个数有几个。
求取单个数
同样的和我们刚刚的这个质数是类似的可以直接求取这个欧拉函数也有求取一个区间的所有欧拉函数值。 def OuLa(n):res ni 2while(i(n//i)):if(n%i0):while(n%i0):n//i#res res* (1-(1/i)) 优化一下避免处于小数res res // i *(i - 1)return res线性筛法求取
这个的话就是求取这个1~n这个范围的所有的欧拉数
def ouLaLiner(n):prim [0] * (n1)st [False] * (n1)cnt 0phi [1] * (n1) # φ(1) 1for i in range(2,n1):if(not st[i]):prim[cnt] ii1phi[i] phi[i-1]j 0while(prim[j]n//i):st[prim[j]*i] Trueif(i%prim[j]0):phi[prim[j]*i] phi[i] *(prim[j])breakphi[prim[j]*i] phi[i] *(prim[j]-1)j1
欧拉定理
那么接下来就是这个欧拉定理这个欧拉定理的话可以用在我们的求逆元的时候用上。
这个定理非常简单。
求逆元 那么这里的话求解的时候的话还需要一个求快速幂的算法
快速幂/幂取模
def KuaiSu(a,k):res 1while(k):if(k%20):res*aa*ak//2return resdef KuaiSu(a,k,p):res 1while(k):if(k%20):res*a % pa*a % pk//2return res原理是这个 (a b) % p (a % p b % p) % p1 (a - b) % p (a % p - b % p ) % p 2 (a * b) % p (a % p * b % p) % p .3 欧几里得算法
求最小公约数
这里的话主要是这个欧几里得算法这个欧几里得算法的话作用还是非常大的一个是求取最小公约数然后的话就是用拓展欧几里得算法来求取这个同余方程当然这块是先用裴蜀定理可以证明一下
def gcd(a,b):if(b0):return areturn (b,a%b)拓展欧几里得算法 我们使用这个拓展欧几里得算法的话可以求出这个来。 我们先来直接看到代码
globe x0,y0
def exgcd(a,b,x,y):if(b 0):x 1,y 0return ad exgcd(b, a % b, y, x);y - (a//b) * x;return d这里的话这个y 是这样的
求解同余方程
那么这个拓展欧几里得算法的话就可以去求解同余方程以及我们刚刚的求逆元。
因为我们那个求逆元其实也就是解一个同余方程只是那个方程比较特殊而已。
为什么可以怎么来的如下 这里的话就不给代码了上面有。然后求逆的话是这样的
