算法之数学知识

发表于 | 更新于: | 分类于 ， | | 阅读数
字数统计: 733 | 阅读时长 ≈ 3

判定质数(试除法)

1
2
3
4
5
6
7
8
9
from math import sqrt

def is_prime(x):
    if x<2:return False
    sup=int(sqrt(x))
    for i in range(2,sup+1):
        if x%i==0:
            return False
    return True

分解质因数(试除法)

1
2
3
4
5
6
7
8
9
10
def divide(x):
    sup=int(sqrt(x))
    for i in range(2,sup+1):
        s=0
        while(x%i==0):
            x//=i
            s+=1
        if s>0:print(i,s,sep="^")
    if x>1:
        print(x,1,sep="^")

求质数表(朴素筛法)

1
2
3
4
5
6
7
8
9
10
def get_primes(n):
    primes=[] # primes[]存储所有素数
    st=[0]*0x3ff # st[x]存储x是否被筛掉，0x3ff表示数据最大范围
    
    for i in range(2,n+1):
        if st[i]: continue
        primes.append(i)
        for j in range(i+i,n+1,i):
            st[j]=1
    return primes

欧几里得算法

最大公约数:

1
2
3
4
5
6
7
8
9
10
# 迭代写法
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
    
# 递归写法
def gcd(a,b):
    if not a%b:return b
    return gcd(b,a%b)

最小公倍数：

1
2
def lcm(a,b):
    return a*b//gcd(a,b)

快速幂(减治)

python内置pow也是快速幂：pow(base,exp[,mod])

注意还有一个是math.pow(x,y)

Unlike the built-in ** operator, math.pow() converts both its arguments to type float.

Use ** or the built-in pow() function for computing exact integer powers

1
2
3
4
5
6
7
8
9
def fastExpMod(a,b,p): # a^b % p
    a=a%p
    ans=1
    while b!=0:
        if b&1:
            ans=(ans*a)%p
        b>>=1
        a=(a*a)%p
    return ans

这里再补充一个小知识：费马小定理

p为质数，a为任意自然数，则

$a^p \equiv a(\mod p)$

或者$a^{p-1} \equiv 1(\mod p)$

求组合数(递归)

计算$C_n^m % p$

利用递推公式：$C^m_n = C^m_{n-1} + C^{m-1}_{n-1}$

1
2
3
4
5
6
7
8
9
def helper(n,m,p): # 实际上把0x3ff范围内的所有组合数都计算出来了
    res=[[0 for _ in range(0x3ff)] for _ in range(0x3ff)] 
    for i in range(0x3ff):
        for j in range(i+1):
            if not j:
                res[i][j]=1
            else:
                res[i][j]=(res[i-1][j]+res[i-1][j-1])%p
    return res[n][m]

求欧拉函数

欧拉函数的定义

1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
若在算数基本定理中，$N=p^{a_1}_1p^{a_2}_2…p^{a_m}_m$，则：
$ϕ(N) = N×\frac{p_1−1}{p1}×\frac{p_2−1}{p2}×…×\frac{p_m−1}p{m}$

1
2
3
4
5
6
7
8
9
10
11
def phi(x):
    res=x
    sup=int(sqrt(x))
    for i in range(2,sup+1):
        if x%i==0:
            res=res/i*(i-1)
            while(x%i==0):
                x/=i
    if x>1:
        res=res/x*(x-1)
    return res

计算n!中有多少个质因子p

1
2
3
def cal(n,p):
    if n<p:return 0
    return n//p+cal(n//p,p)

约数

如果 $N = p_1^{c_1} * p_2^{c_2} * … *p_k^{c_k}$
约数个数：$ (c_1 + 1) * (c_2 + 1) * … * (c_k + 1)$
约数之和：$ (p_1^0 + p_1^1 + … + p_1^{c_1}) * … * (p_k^0 + p_k^1 + … + p_k^{c_k})$

卡特兰数

给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为：

$ Cat(n) = \frac{C_{2n}^{n}} {(n + 1)}$

不要打赏，只求关注呀QAQ