算法模板Part Four - 数论

数论

质数

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

试除法判定质数

bool is_prime(int n)
{
	if (n < 2) return false;
    for (int i = 2; i < n; i ++ )
        if (n % i == 0) return false;
   	return true;
}

优化: 若$ d|n $，则 $ {n d} | n $。 $ d n d$ ，\(d^2 \leq n\) ，枚举到 \(d \leq \sqrt n\)

细节：i * i 有溢出风险，i <= n / i 这样写比较好。

时间复杂度： \(O(\sqrt n)\)

bool is_prime(int n)
{
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i ++ )
        if (n % i == 0) return false;
   	return true;
}

分解质因数

\[ n = p_1^{x_1} \times p_2^{x_2} \times \dots \times p_k^{x_k} \]

从小到大枚举所有数，若能整除就继续除。

细节：合数会被素数筛掉

for(int i = 2; i <= n; i ++ )
{
    if (n % i == 0) // i一定是质数
    {
        int s = 0;
        while (n % i == 0)
        {
            n /= i;
            s ++ ;
        }
        printf("%d %d\n", i, s);
    }
}

优化：n中最多只包含一个大于 \(\sqrt n\) 的质因子

时间复杂度：最慢 \(O(\sqrt n)\)，最快 \(O(\log n)\)，如 \(n = 2^k\) 时。

for(int i = 2; i <= n / i; i ++ )
    if (n % i == 0) // i一定是质数
    {
        int s = 0;
        while (n % i == 0)
        {
            n /= i;
            s ++ ;
        }
        printf("%d %d\n", i, s);
    }

if (n > 1) printf("%d %d", n, 1); // 单独处理最后一个数
puts("");

筛质数

先把从2开始到n的所有的数写到一个数表里，从前往后把每个数的倍数删掉。 对于p而已，若它没被删掉，则说明2~p-1都不是其因子，故p是质数。

时间复杂度：\(O(n \log n)\)

i = 2，循环了 \(\frac n 2\) 次； i= 3， 循环了 \(\frac n 3\) 次； ... \[ \frac n 2 + \frac n 3 + \dots + \frac n k = n(\frac 1 2 + \dots + \frac 1 k) = n \ln n \]

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
        }
        for (int j = i + i; j <= n; j += i) st[j] = true; // true标记删除
    }
}

埃氏筛法

优化：并不需要把每个数的倍数删掉，只需要把质数的所有倍数删掉，2~p-1中的质数判断是不是p的约数即可。合数都可以通过比它小的质数表示出来，筛了质数的倍数自然而然合数也就被筛掉了。

质数定理：1~n中有 \(\frac n {\ln n}\) 个质数

时间复杂度： \(O(n \log\log n)\) 例如\(n = 2^{32}\) , \(\log {\log n} = 5\)

int primes[N], cnt; // cnt记录质数的个数
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i; // primes存质数
            for (int j = i * 2; j <= n; j += i) st[j] = true; // true标记删除，可能会重复标记
        }
    }
}

线性筛法

核心：合数 \(n\) 只会被它的最小质因子筛掉一次(线性)， 任何一个合数一定会被筛掉

时间复杂度：\(O(n)\)， \(n = 10^7\)时，比埃氏筛法约快一倍，\(n = 10^6\)，两个差不多

因为从小到大枚举，i % primes[j] == 0 发生时，意味着 primes[j] 一定是 i 的最小质因子，因此 primes[j] 也一定是 i*primes[j] 最小质因子。当 i % primes[j] != 0 ，由于是从小到大枚举质数并且没有没有枚举到过 i 的任何一个质因子，说明 primes[j] 一定小于 i 的任何一个质因子，因此 primes[j] 也一定是 i*primes[j] 最小质因子。

任何一个合数一定会被筛掉：因为任何一个合数x， 一定存在最小质因子，假设 primes[j] 是x的最小质因子，当i枚举到 x/primes[j] 的时候，x就被筛掉了。

没必要 j < cnt ，因为如果说 i 是合数的话，当 primes[j] 枚举到 i 的最小质因子的时候就一定会停下来；当 i 是质数的时候 ，当primes[j] == i 的时候也会停下来。 primes[j] * i 是当前要筛的数，这个数是在n的范围内，就是小于等于n

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    // 第一个循环要枚举出1~n中的所有质数，所以要枚举到n，第二个循环要筛的数是 primes[j] * i，这个数不能超过n。
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ) // j从小到大枚举所有质数
        {
            st[primes[j] * i] = true; // 每次把当前质数和i的乘积 (一个合数) 筛掉
            if (i % primes[j] == 0) break;  // 第一次枚举到i的质因子就break
        }
    }
}

约数

试除法求约数

一个数的所有约数成对出现，边界 i 和 n / i 相同话只加一个

时间复杂度：\(O(\sqrt n + \log n \log \log n)\) = $O(n) $

约数的个数等于倍数的个数， 1~n中有 \(n + \frac n 2 + \frac n 3 + \dots = n\ln n\) 个约数，期望每个数有$ n$个约数。

vector<int> get_divisors(int n)
{
    vector<int> res;
    
    for (int i = 1; i <= n / i; i ++ )
        if (n % i == 0)
        {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    sort(res.begin(), res.end()); //对约数排序
    return res;
}

约数个数

对于\(n = p_1^{x_1} \times p_2^{x_2} \times \dots \times p_k^{x_k}\)，约数个数为 \((x_1 + 1)(x_2 + 1) ... (x_k + 1)\)，因为n的任何一个约数\(d\)都可以表示为 \(p_1^{\beta_1} \times p_2^{\beta_2} \times \dots \times p_k^{\beta_k}\) , 其中 \(0 \leq \beta _i \leq x_i\) 。每个 \(\beta\) 的取法有 \(x+1\) 种。

int 范围内，约数个数最多的数其约数大概有 1536 个。

int get_cnt(int n)
{
    int res = 1;
    for (int i = 2; i <= n / i; i ++ )
    {
        int s = 0;
        while (n % i == 0)
        {
            n /= i;
            s ++ ;
        }
        if(s) res = res * (s + 1);
    }
    if (n > 1) res *= 2;
    return res;
}

约数之和

\[ (p_1^0 + p_1^1 + \dots +p_1^{\alpha_1})(p_2^0 + p_2^1 + \dots +p_2^{\alpha_2})\dots(p_k^0 + p_k^1 + \dots +p_k^{\alpha_k}) = \prod_{i = 1}^{k} \frac {1 - p_i^{\alpha_i + 1}} {1 - p_i} \]

展开后就是约数之和，且取遍了每一个约数。

不用等比数列公式，因为会溢出，不好处理。 \[ t = p \times t + 1 \\ t = 1,t = p + 1,t = p^2 + p + 1,...,t = p^{\alpha} + ... + p + 1 \]

typedef long long LL;

const int MOD = 1e9 + 7;

unordered_map<int, int> primes;

for (int i = 2; i <= x / i; i ++ )
{
	while (x % i == 0)
    {
        x /= i;
        primes[i] ++ ;
    }
    if (x > 1) primes[x] ++ ;
}

LL res = 1;
for (auto prime : primes)
{
    int p = prime.first, a = prime.second;
    LL t = 1;
    while (a -- ) t = (t * p + 1) % MOD; // 秦九韶算法
    res = res * t % MOD;
}

最大公约数

欧几里得算法(辗转相除法)

若d能整除a, 即 \(d | a\)，且 \(d | b\)，则 \(d | (ax + by)\)。 a 和 b 的最大公约数等于 b 和 \(a\enspace mod \enspace b\) 的最大公约数 。 \[ (a, b) = (b, a\enspace mod \enspace b) \] 边界：0除以任何一个数都得0，可以整除。所有0和一个数的最大公约数是这个数本身， 即 \(gcd(a, 0) =gcd(0, a)= a\) 。

时间复杂度：\(O(\log n)\)

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

欧拉函数

\(\varphi(n)\)： 1~n中与n互质的数的个数，互质即最大公约数为1 。

公式如下： \[ \varphi(N) = N (1 - \frac 1 {p_1})(1 - \frac 1 {p_2})\dots(1 - \frac 1 {p_k}) \] 性质：若 \(a\) 与 \(b\) 互质，则 \(a^{\varphi(b)} \ \% \ b \equiv 1\) 。当b是质数p时，有费马小定理 \(a^{p - 1} \equiv 1 (mod \ p)\) 。

展开等于容斥原理：

1. 从1~N中去掉\(p_1, p_2, ... p_k\)的所有倍数
2. 加上所有 \(p_i *p_j\) 的倍数
3. 减去所有\(p_i * p_j * p_k\)的倍数，以此类推

\[ N - \frac N {p_1} - \frac N {p_2} - ... + \frac N {p_1*p_2} + ... - \frac N {p_1*p_2*p_3} - ... + ... \]

int get_euler(int a)
{
    int res = a;
    for (int i = 2; i <= a / i; i ++ )
    {
        while (a % i == 0) 
        {
            res = res / i * (i - 1);  // 先除后乘
            a /= i; // 分解质因数
        }
    }
    if (a > 1) res = res / a * (a - 1);
    return res;
}

筛法求欧拉函数

若 \(p_j\) 是 \(i\) 的质因子：\(\varphi(p_j * i) = p_j\varphi(i)\) 若 \(p_j\) 不是 \(i\) 的质因子：\(\varphi(p_j * i) = p_j(1-\frac 1 {p_j})\varphi(i)=(p_j - 1)\varphi(i)\)

typedef long long LL;

int primes[N], cnt;
int phi[N];
bool st[N];

LL get_eulers(x)
{
	phi[1] = 1;
    for (int i = 2; i <= x / i; i ++ )
    {
        if (!st[i]) 
        {
            primes[cnt ++ ] = i;
            phi[i] = i - 1;
        }
        
        for (int j = 0; primes[j] <= x / i; j ++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) // primes[j]是i的质因子
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1); 
        }
    }
    LL res = 0;
    for (int i = 1; i <= x; i ++ ) res += phi[i];
    
    return res;
}

快速幂

快速求出 \(a^k\;mod \;p\) 的结果 \((1 \leq a, k, p \leq 10^9)\)

时间复杂度: \(O(\log k)\)

核心思路：反复平方法，预处理出 \(a^{2^0} mod {\ }p\)，\(a^{2^1} mod {\ }p\)，\(a^{2^2} mod {\ }p\)，...，\(a^{2^{\log k}} mod \ p\)，每一个数都是前一个数的平方模 \(p\) 。

\(a^k = a^{2^i + 2^j + \dots + 2^t} = a^{2^i}\times a^{2^j} \times \dots \times a^{2^t}\)，k的二进制表示为1的位对应\(i,j, ...t\)。

typedef long long LL;

// a^k % p
int qmi(int a, int k, int p)
{
    int res = 1 % p; // p = 1时, res = 0
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p; // 更新a
    }
    return res;
}

乘法逆元的定义

若整数b，m互质，并且 \(b | a\)，则存在一个整数 \(x\) ，使得 \(\frac a b = a \times x \;(mod \; m)\) ，则称 \(x\) 为 \(b\) 的模 \(m\) 乘法逆元，记为 \(b^{−1}(\mod m)\)。 \(b\) 存在乘法逆元的充要条件是 \(b\) 与模数 \(m\) 互质。当模数 \(m\) 为质数时，\(b^{m−2}\) 即为 \(b\) 的乘法逆元。