最大公因数

1
2
3
4
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

最小公倍数

$ a b = gcd(a,b) lcm(a,b) $

1
2
3
4
5
def lcm(a,b):
    s=a*b
    while b:
        a,b=b,a%b
    return s//a

素数筛

判断素数

1
2
3
4
5
def isprime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True

埃氏筛

时间复杂度：O(nloglogn) 

1
2
3
4
5
6
7
8
9
10
11
12
13
maxn=10000#这个范围自己依据要查找数据范围内的质数设定
 
is_prime=[True for i in range(maxn+1)]
 
prime=[] #记录质数

for i in range(2,maxn):
    if is_prime[i]:
        prime.append(i)
        j=i**2#从i方开始筛，因为前面的2i，3i等已经是2,3等的倍数了
        while j<=maxn:
            is_prime[j]=False
            j+=i

欧拉筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
maxn=10000#这个范围自己依据要查找数据范围内的质数设定
 
is_prime=[True for i in range(maxn+1)]
 
prime=[] #记录质数

for i in range(2,maxn):
    if is_prime[i]:
        prime.append(i)
    for p in prime:
        if i*p>maxn:
            break
        is_prime[i*p]=False
        if i%p==0:
            break#确保被其最小素数筛掉一次

唯一分解定理

1
2
3
4
5
6
7
8
9
def prime_factor(n):
    factors=[]
    for i in range(2,n**0.5+1):
        while n%i==0:
            n//=i
            factors.append(i)
        if n==1:
            break
    return factors

快速幂

直接pow(a,b)或pow(a,b,p)好了www

1
2
3
4
5
6
7
8
9
def fast_power(a,b,p):
    ans=1
    a%=p
    while b:
        if b%2==1:  
            ans=(ans*a)%p
        a=(a*a)%p
        b//=2
    return ans

乘法逆元

费马小定理

当m为质数的时候：

1
2
def mod_inverse_fermat(a, m):
    return pow(a, m - 2, m)

扩展欧几里得算法

1
2
3
4
5
6
7
def ext_gcd(a, b): #扩展欧几里得算法    
    if b == 0:          
        return 1, 0, a     
    else:         
        x, y, gcd = ext_gcd(b, a % b)      
        x, y = y, (x - (a // b) * y)         
        return x, y, gcd