数学python模板

求n!

from math import factorial
factorial(n)   # 返回 n!

快速幂

p = 998244353
def fastpow(a, n):
    base, res = a, 1
    while n != 0:
        if n & 1: #取最后一位二进制数，看是否为1
            res = res * base % p
        base = base * base % p
        n >>= 1
    return res%p
"""自带的快速幂"""
pow(a,b,p) # a^b mod p

第二类斯特林数

class Factorial:
    def __init__(self, N, mod) -> None:
        self.mod = mod
        self.f = [1 for _ in range(N)]
        self.g = [1 for _ in range(N)]
        for i in range(1, N):
            self.f[i] = self.f[i - 1] * i % self.mod
        self.g[-1] = pow(self.f[-1], mod - 2, mod)
        for i in range(N - 2, -1, -1):
            self.g[i] = self.g[i + 1] * (i + 1) % self.mod
 
    def comb(self, n, m):
        if n < 0 or m < 0 or n < m:
            return 0
        return self.f[n] * self.g[m] % self.mod * self.g[n - m] % self.mod
 
    def perm(self, n, m):
        if n < 0 or m < 0 or n < m:
            return 0
        return self.f[n] * self.g[n - m] % self.mod
 
    def catalan(self, n):
        # TODO: check 2 * n < N#
        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod
 
    # N个不同的物品放进m个不同的集合，保证每个集合都不是空集#
    def sterling(self, n, m):
        if n < m:
            return 0
        else:
            res = 0
            for i in range(m + 1):
                t = self.comb(m, i) * pow(m - i, n, self.mod) % self.mod
                if i & 1:
                    res -= t
                else:
                    res += t
                res %= self.mod
            return res * self.g[m] % self.mod
         
n,m = map(int,input().split())
t = Factorial(n+1,int(1e9) + 7)
print(t.sterling(n,m))

1、质数

从 到 中有 个质数

(1) 判定（试除法）

def is_primer(n):
	i = 2
    while i <= n // i:
        if n % i == 0: return False
        i += 1
    return True

(2)分解质因数（试除法）

primes,c = [],[]
def divide(n):
    i = 2
    while i*i <= n:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                n //= i
                cnt += 1
            primes.append(i)    # i 为质因数，cnt 为对应的指数
            c.append(cnt)
        i += 1
    if n > 1:
        primes.append(n)
        c.append(1)

如果有多次询问：当然可以预处理质数O(sqrt(n)),每次询问O(sqrt(n)/log(n))

(3)埃氏筛法

ls, primes = [0]*(n+1), []
def get_primes(n):
    for i in range(2, int(sqrt(n))+1):
        if not ls[i]:
            primes.append(i)
            for j in range(i+i, n+1, i):
                ls[j] = 1

(4)埃氏筛变形：区间筛

对于给定区间 ，

MAXN = 46400  #sqrt(2147483647)
prime = []
is_prime = [1] * MAXN

for i in range(2, MAXN):
    if is_prime[i]:
        prime.append(i)
        for j in range(i*i, MAXN, i):
            is_prime[j] = 0
def solve():
    l, r = map(int, sys.stdin.readline().split())
    if l == 1: l += 1  #不处理的话,1会筛不掉
    n = r - l + 1
    if n < 2: return
    vis = [0] * n
    for p in prime:
        if p > r: break
        for i in range((l+p-1)//p * p, r//p*p+1, p):
            if i == p: continue
            vis[i-l] = 1
    ls = []
    for i in range(n):
        if vis[i]: continue
        ls.append(i)

(5)线性筛法（确保了每个被筛掉的合数都是由其最小质因子筛掉的）

当 时，由于我们是从小到大遍历质数，所以 是 的最小质因子，也是 的最小质因子。

当 时， 小于 的最小质因子，所以也是 的最小质因子。

N = 3*10**5
is_prime = [1]*(N+1)
primes = []
for i in range(2,N+1):
    if is_prime[i]: primes.append(i)
    j = 0
    while primes[j] <= N//i:
        is_prime[primes[j]*i] = 0
        if i % primes[j] == 0: break
        j += 1

2、约数

(1)扩展欧几里得算法

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

所以：

又 $a \mod b = a - a//bbax + by = b(x’ - a//by’) + ay’ = d$

即：

def exgcd(a, b):
    if b == 0: return [a, 1, 0]
    [g, x, y] = exgcd(b, a % b)
    return [g, y, x - a // b * y]

ex_gcd解方程技巧

假设 ax+by = (a,b) 的一组解为，则通解为：，

有解当且仅当 ，特解为

假设要解方程 ，只要 互为质数，那么解出来 后再乘个 就是上述方程的解

3、同余与模

• 判定在 里 a 是否有逆元
• 如果有如何求解逆元

考虑 有解，当且仅当 互质，如果 为质数，则 ~ 在模 的情况下有逆。

欧拉定理

如果 ，那么 ，其中 是欧拉函数。

费马小定理

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

乘法逆元的三种求法

• 扩展欧几里得算法：，已知 求
• 欧拉定理：设 为正整数， 且 ，
• 费马小定理：当模数 为质数时 即为 的乘法逆元