目录

质数,约数,快速幂,逆元,排列组合

----------------------------------------------分割线-------------------------------------------------

质数

试除法判定质数

O($\sqrt{n}$)

def isPrime(num):
    if num <= 1:return False
    x = 2
    while x <= num // x:
        if num % x == 0:
            return False
        x += 1
    return True

分解质因数

O($\log{n}$) ~ O($\sqrt{n}$)

def deal(x):
    factor = 2
    while factor <= x // factor:
        if x % factor == 0:
            cnt = 0
            while x % factor == 0:
                cnt += 1
                x //= factor
            print(factor, cnt)
        factor += 1
    #当x=1时，表示已经求得所有素因子,显然，大于sqrt(x)的因子个数最多1个
    if x > 1: print(x, 1)

筛质数

O($n\log{\log{n}}$)

int getPrimeNum(int n){
    int cnt = 0
    for (int i = 2; i <= n; i ++ ){
        if (st[i]) continue;
        cnt ++;
        for (int j = i + i; j <= n; j += i) st[j] = true;
    }
    return cnt;
}

----------------------------------------------分割线-------------------------------------------------

约数

最大公约数

def gcd(a, b):
    while b:
        t = a
        a = b
        b = t % b
    return a

----------------------------------------------分割线-------------------------------------------------

快速幂

快速幂

def gcd(a, p, k):
    ans = 1
    while p:
        if p & 1:ans = ans * a % k
        a = a * a % k
        p >>= 1
    return ans

----------------------------------------------分割线-------------------------------------------------

逆元

逆元

如果b*x ≡ 1 (mod p),则称x为b模p的乘法逆元,且a / b ≡ a * x (mod p)
逆元存在的充要条件:gcd(b, m) = 1
由于b*x ≡ 1 (mod p),故b * x - 1 = k * m <=> b * x - k * m = 1, 利用扩展欧几里得算法求解即可

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b,a % b,x,y);
    int u = x,v = y;
    x = v;
    y = u - a / b * v;
    return d;
}

(a + b) % p = 0 <=> (a + b) % p = 0 % p <=> a + b ≡ 0 (mod p) <=> a ≡ -b (mod p)
由此有当k < p时，有 (a + b) % p = k <=> a ≡ k - b (mod p)
----------------------------------------------分割线-------------------------------------------------

排列组合

C(a, b) = C(a - 1, b - 1) + C(a - 1, b)
C(a, b) = b! / a! / (a - b)!
C(a, b) ≡ C(a / p, b / p) * C(a % p, b % p) (mod p)