基础数学知识 / Math（updating）

埃氏筛：朴素筛法求素数，o(nloglogn)

int prime[N], tot;

bool st[N]; // true:not prime, false:is prime

void get_primes(int n)

{

    st[1] = true;

    for(int i = 2; i <= n; i++)

    {

        if(!st[i])

        {

            prime[++tot] = i;

            for(int j = i + i; j <= n; j += i) st[j] = true;

        }

    }

}

欧拉筛：线性筛法求素数，o(n)

int prime[N], tot;

bool st[N]; // true:not prime, false:is prime

void get_primes(int n)

{

    st[1] = true;

    for(int i = 2; i <= n; i++)

    {

        if(!st[i]) prime[++tot] = i;

        for(int j = 1; i * prime[j] <= n; j++)

        {

            st[i * prime[j]] = true;

            if(i % prime[j] == 0) break;

        }

    }

}

约数个数 & 约数之和

如果 N = p₁^c₁ * p₂^c₂ * p₃^c₃* ... * pk^c_k

约数个数：cnt = ( c₁ + 1 ) * ( c₂ + 1 ) * ( c₃ + 1 ) * ... * ( c_k + 1 )

unordered_map<int, int> primes;

int cal(int x)

{

    //分解质因数

    for(int i = 2; i*i <= x; i++)

        if(x % i == 0) while(x % i == 0) primes[i] ++, x /= i;

    if(x > 1) primes[x] ++;

    //计算约数个数

    int cnt = 1;

    for(auto p : primes) cnt = cnt * (p.second + 1) % mod;

    return cnt;

}

约数之和：sum = ( p₁⁰ + p₁¹ + ... + p₁^c₁ ) * ... * ( p_k⁰ + p_k¹ + ... + p_k^c_k )

unordered_map<int, int> primes;

int cal(int x)

{

    //分解质因数

    for(int i = 2; i*i <= x; i++)

        if(x % i == 0) while(x % i == 0) primes[i] ++, x /= i;

    if(x > 1) primes[x] ++;

    //计算约数之和

    int sum = 1;

    for(auto p : primes)

    {

        int a = p.first, b = p.second;

        int res = 1;

        while(b--) res = (res * a + 1) % mod;

        sum = sum * res % mod;

    }

    return sum;

}

欧几里得算法：求最大公约数

int gcd(int a, int b)

{

    return b ? gcd(b, a % b) : a;

}

快速幂：快速求某数的次幂

int qmi(int m, int k, int p)

{

    int res = 1 % p;

    while(k)

    {

        if(k&1) res = res * m % p;

        m = m * m % p;

        k >>= 1;

    }

    return res;

}

欧拉函数：φ(n):小于或等于n的正整数中与n互质的数的数目

设 N = p₁^c₁ * p₂^c₂ * p₃^c₃* ... * pk^c_k

则 φ(N) = N * ( 1 - 1/p₁ ) * ( 1 - 1/p₂ ) * ( 1 - 1/p₃ ) * ... * (1 - 1/p_k )

朴素算法：o(n^1/2) // n为所求数的大小

int phi(int x)

{

    int res = x;

    for(int i = 2; i*i <= x; i++)

        if(x % i == 0)

        {

            res = res / i * (i - 1); // res = res * (1 - 1/i)

            while(x % i == 0) x /= i;

        }

    if(x > 1) res = res / x * (x - 1);

    return res;

}

筛法求欧拉函数：o(n) // n为求欧拉函数的数的个数

int primes[N], tot, euler[N];

bool st[N];

void get_euler(int n)

{

    euler[1] = 1;

    for(int i = 2; i <= n; i++)

    {

        if(!st[i])

        {

            primes[++tot] = i;

            euler[i] = i - 1;

        }

        for(int j = 1; i * primes[j] <= n; j++)

        {

            int t = i * primes[j];

            st[t] = true;

            if(i % primes[j] == 0)

            {

                euler[t] = euler[i] * primes[j];

                break;

            }

            // euler[t] = euler[i] * primes[j] * (1 - 1/primes[j])

            euler[t] = euler[i] * (primes[j] - 1);

        }

    }

}

欧拉定理：若a、p为正整数，且互素，则a^φ(p) ≡ 1 (mod p)

用欧拉定理直接求乘法逆元的代码量较大且时间复杂度较高，不太建议。

费马小定理：若a、p为正整数，且p为素数，则a^p-1 ≡ 1 (mod p) （欧拉定理的特殊情况）

故当满足以上条件时(模数p为素数)，可用费马小定理结合快速幂求乘法逆元：

int qmi(int m, int k, int p)

{

    int res = 1 % p;

    while(k)

    {

        if(k&1) res = res * m % p;

        m = m * m % p;

        k >>= 1;

    }

    return res;

}

int inv(int a, int p)

{

    return qmi(a, p-2, p);

}

裴蜀定理

对于任意正整数a、b，一定存在整数x、y，使得 ax + by = gcd(a, b)

并且假设有ax₀ + by₀ = gcd(a, b)，

则有通解：x = x₀ + K·(b/d)，y = y₀ - K·(a/d) ( d = gcd(a, b)，K ∈ Z ) .

其中，求解x_0、y₀的构造见扩展欧几里得算法

扩展欧几里得算法：求x, y，使得ax + by = gcd(a, b)

int exgcd(int a, int b, int &x, int &y)

{

    if (!b)

    {

        x = 1; y = 0;

        return a;

    }

    int d = exgcd(b, a % b, y, x);

    y -= (a/b) * x;

    return d;

}

应用：解线性同余方程、求乘法逆元

// 拓展欧几里得算法求逆元

int exgcd(int a, int b, int &x, int &y)

{

    if (!b)

    {

        x = 1; y = 0;

        return a;

    }

    int d = exgcd(b, a % b, y, x);

    y -= (a/b) * x;

    return d;

}

int inv(int a, int p)

{

    int x, y;

    int g = exgcd(a, p, x, y);

    return g != 1 ? -1 : (x % p + p) % p; //返回-1表示乘法逆元不存在

}

约瑟夫问题

n 个人标号0~n-1，逆时针站一圈。从0号开始，每一次从当前的人逆时针数k个，然后让这个人出局。问最后剩下的人是谁。

线性算法：

int josephus(int n, int k)

{

    int res = 0;

    for(int i = 1; i <= n; i++) res = (res + k) % i;

    return res; //若编号从1开始则res+1, 从0开始则不需要

}

欧拉降幂

巴特西

基础数学知识 / Math（updating）

最新文章

热门文章