首页 > 其他分享 >「外出学习」数论学习笔记

「外出学习」数论学习笔记

时间：2023-05-28 11:46:52浏览次数：44  
标签：gcd 数论 dfrac bmod 笔记 学习 int bmatrix cdot

取模

\[(1) \quad 5 \div 3 = 1 \cdots 2\\ a = b \cdot c + d\\ (2) \quad a \div b = c \cdots d\\ b > d \ge 0\\ (3) \quad a, b, c = a / b, d = a \bmod b\\ (4) \quad (a + b) \bmod c = [a \bmod c + b \bmod c] \bmod c\\ a = x \cdot c + a', b = y \cdot c + b'\\ (xc + a' + yc + b') \bmod c = (a' + b') \bmod c\\ \]

模运算

\[(a + b) \bmod c = (a \bmod c + b \bmod c) \bmod c\\ (a - b) \bmod c = (a \bmod c - b \bmod c) \bmod c\\ (a \cdot b) \bmod c = [(a \bmod c) \cdot (b \bmod c)] \bmod c\\ \]

#include <iostream>
using namespace std;

int a, b, c;

int main() {
    cin >> a >> b >> c;
    cout << (a + b) % c << endl;
    cout << ((a - b) % c + c) % c << endl;
    cout << ((long long)a * b) % c << endl;
    cout << (1ll * a * b) % c << endl;
    return 0;
}

读入两个数 \(n, p\)，现在求 \((n!) \bmod p\) 是多少？\((2 < p \le 10^9, 1 \le n \le 1000)\)

#include <iostream>
using namespace std;

int n, p;

int main() {
    cin >> n >> p;
    int ans = 1;
    for (int i = 1; i <= n; ++ i) {
        ans = 1ll * ans * i % p;
    }
    cout << ans << endl;
    return 0;
}

\[n! \bmod p = [(n - 1) ! \bmod p \times n \bmod p] \bmod p \]

gcd、lcm

\(\gcd\):最大公因数。

\(\operatorname{lcm}\):最小公倍数。

有两个数 \(a, b\)，求 \(\gcd(a, b)\)。

\[\begin{aligned} & 设 \gcd(a, b) = g，则 g | a 且 g | b。\\ & \therefore a = a'g, b = b'g\\ & \therefore \gcd(a', b') = 1, 即 a' \perp b'\\ & \gcd(a, b) = \gcd(a - b, b) \end{aligned} \]

\[g = \gcd(a, b) = \gcd(a - b, b)\\ a = a'g, b = b'g\\ \gcd(a', b') = 1\\ \gcd(a - b, b) = \gcd[(a' - b')g, b'g] = \gcd(a' - b', b') \cdot g\\ \begin{aligned} & \because \gcd(a', b') = 1\\ & \therefore \gcd(a' - b', b') = 1\\ & \therefore \gcd(a - b, b) = g\\ \end{aligned}\\ \begin{aligned} &\quad \gcd(a, b)\\ &= \gcd(a - b, b)\\ &= \gcd(a - b - b, b)\\ &= \gcd(a - b - b - b, b)\\ &= \cdots\\ &\gcd(a, b) = \gcd(a \bmod b, b)\\ \end{aligned} \]

// gcd(a, 0) = a
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

证明以上代码是 \(\log\) 复杂度。

\[\gcd(a, b) \Rightarrow \gcd(b, a \bmod b) \quad(a \ge b)\\ a \bmod b < \dfrac{1}{2}a\\ \]

\[a \bmod b < \dfrac{1}{2}d\\ (1) \quad b \le \dfrac{1}{2}a\\ a \bmod b < b \le \dfrac{1}{2}a\\ (2) \quad b \ge \dfrac{1}{2}a\\ a - b \cdot 1 = a - b < \dfrac{1}{2}a \]

每次都砍一半，所以这是一个 \(\log\) 复杂度的算法。

有 \(n\) 个数，\(a_1, a_2, a_3, \cdots, a_n\)，求这 \(n\) 个数的 \(\gcd\)。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n;
int a[N];

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
    }
    int ans = a[1];
    for (int i = 2; i <= n; ++ i) {
        ans = gcd(ans, a[i]);
    }
    cout << ans << endl;
    return 0;
}

复杂度：\(O_{n + \log{a}}\)，因为 ans 只能越来越小。

\[\gcd(a, b) = g, \operatorname{lcm}(a, b) = l\\ a \cdot b = g \cdot l\\ l = \dfrac{a\cdot b}{g} \]

lcm(a, b) = a / gcd(a, b) * b;

计算 \(x ^ y \bmod p\)。\((x, y, p \le 10^9)\)

#include <bits/stdc++.h>
using namespace std;

int x, y, p;

int qpow(int x, int y, int p) {
    if (y == 0)    return 1;
    int z = qpow(x, y / 2, p);
    z = 1ll * z * z % p;
    if (y & 1) {
        z = 1ll * z * x % p;
    }
    return z;
}

int main() {
    cin >> x >> y >> p;
    cout << qpow(x, y, p);
    return 0;
}

给你三个数 \(x, y, p\)，计算 \(x \cdot y \bmod p\)。\((x, y, p \le 10^{18})\)，同时不支持 __int128。

\[x \cdot 37 = x + x + x + \cdots + x\\ x \cdot 37 = x \cdot 18 + x \cdot 18 + x\\ x \cdot 18 = x \cdot 9 + x \cdot 9\\ \]

将乘法转化为加法。

int qtimes(int x, int y, int p) {
    if (y == 0)    return 0;
    int z = qtimes(x, y / 2, p);
    z = (z + z) % p;
    if (y & 1) {
        z = (1ll * z + x) % p;
    }
    return z;
}

矩阵

\(n\) 行 \(m\) 列的二维数组就是一个 \(n\) 行 \(m\) 列的矩阵。

矩阵加法

把对应位置上的数加起来就行了。

\[\begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ \end{bmatrix} + \begin{bmatrix} 2 & 3 & 3\\ 2 & 3 & 3\\ \end{bmatrix} = \begin{bmatrix} 3 & 5 & 6\\ 6 & 8 & 9\\ \end{bmatrix} \]

矩阵减法

对应位置上的数相减。

\[\begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ \end{bmatrix} - \begin{bmatrix} 2 & 3 & 3\\ 2 & 3 & 3\\ \end{bmatrix} = \begin{bmatrix} -1 & -1 & 0\\ 2 & 2 & 3\\ \end{bmatrix} \]

数乘矩阵

\[2 \cdot \begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ \end{bmatrix} = \begin{bmatrix} 2 & 4 & 6\\ 8 & 10 & 12\\ \end{bmatrix} \]

矩阵乘法

矩阵 \(A\) 能与矩阵 \(B\) 做乘法，当且仅当 \(A\) 是 \(n\) 行 \(m\) 列，\(B\) 是 \(m\) 行 \(k\) 列。

（只有当第一个矩阵的列数等于第二个矩阵的行数是才能进行矩阵乘法，结果矩阵的行是第一个矩阵的行，列是第二个矩阵的列数）

\[\begin{bmatrix} 1 & 2\\ 3 & 4\\ \end{bmatrix} \times \begin{bmatrix} 1 & 2 & 3\\ 2 & 3 & 3\\ \end{bmatrix} = \begin{bmatrix} 5 & 8 & 9\\ 11 & 18 & 21\\ \end{bmatrix} \]

struct matrix {
    int n, m;
    int z[10][10];
    matrix() { // 构造函数
        n = m = 0;
        memset(z, 0, sizeof(z));
    }
};
matrix m1, m2, m3;

matrix operator * (const matrix &m1, const matrix &m2) { // 重载运算符
    matrix m;
    m.n = m1.n, m.m = m2.m;
    for (int i = 1; i <= m.n; ++ i) {
        for (int j = 1; j <= m.m; ++ j) {
            for (int k = 1; k <= m1.m; ++ k) {
                m.z[i][j] += m1.z[i][k] * m2.z[k][j];
            }
        }
    }
    return m;
}

m3 = m1 * m2;

memset

memset(z, 0, sizeof z);
memset(z, -1, sizeof z);
memset(z, 0x3f, sizeof z); // 赋成 0x3f3f3f3f

给两个数 \(n, p\)，求斐波那契而数列第 \(n\) 项 \(f_n \bmod p\) 是多少。\((n, p) \le 10^9\)

暴力

cin >> n >> p;
int a = 0, b = 1;
for (int i = 2; i <= n; ++ i) {
    int c = a + b;
    if (c >= p)    c -= p;
    a = b, b = c;
}

\[\begin{bmatrix} f_{i - 1} & f_{i - 1} \end{bmatrix} \times \begin{bmatrix} 1 & 1\\ 1 & 0\\ \end{bmatrix} = \begin{bmatrix} f_i & f_{i - 1} \end{bmatrix}\\ \begin{bmatrix} f_i & f_{i - 1} \end{bmatrix} \times \begin{bmatrix} 1 & 1\\ 1 & 0\\ \end{bmatrix} = \begin{bmatrix} f_{i + 1} & f_i\\ \end{bmatrix}\\ \begin{bmatrix} f_1 & f_0\\ \end{bmatrix} \times \begin{bmatrix} 1 & 1\\ 1 & 0\\ \end{bmatrix} ^ n = \begin{bmatrix} f_{n + 1}, f_n\\ \end{bmatrix} \]

matrix qpow(matrix x, int y) {
    if (y == 1)    return x;
    matrix z = qpow(x, y / 2);
    z = z * z;
    if (y & 1)    z = z * x;
    return z;
}

int main() {
    cin >> n >> p;
    matrix A, B;
    A.n = 1, A.m = 2;
    A.z[1][1] = 1, A.z[1][2] = 0;
    B.n = 2, B.m = 2;
    B.z[1][1] = 1, B.z[1][2] = 1;
    B.z[2][1] = 1, B.z[2][2] = 0;
    matrix C = A * qpow(B, n);
    int ans = C.z[1][2];
    cout << ans % p << '\n';
    return 0;
}

矩阵乘法没有交换律，有结合律。

有 \(n\) 个点，走 \(k\) 步，走到 \(n\) 号点的方案数。\((n \le 100, k \le 10^9)\)

设 \(f(i, j)\) 为走了 \(i\) 步，走到了 \(j\) 的方案数。

\(f(0, 1) = 1, f(0, 2) = f(0, 3) = \cdots =f(0, n) = 0\)

\(f(i, j) = f(i - 1, p_1) + f(i - 1, p_2) + f(i - 1, p_3) + \cdots\)

cin >> n;
for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= n; ++ j) {
        cin >> z[i][j];
    }
}
f[0][1][1] = 1;
for (int a = 1; a <= k; ++ a) { // 走了a步
    for (int d = 1;d <= 1; ++ d) { // 凑矩阵
        for (int b = 1; b <= n; ++ b) { // 走到了b
            for (int c = 1; c <= n; ++ c) { // 第a-1步在c
                f[a][d][b] += f[a - 1][d][c] * z[c][b];
            }
        }
    }
}
cout << f[k][1][n] << '\n';
return 0;

我们可以把 f[a], f[a-1], z 看成矩阵。

即 \(f_a = f_{z - 1} \times z\)

\(a_k = f_0 \times z^k\)

P4159

拆点，一条长度为 \(5\) 的边拆成五条长度为 \(1\) 的边。

cin >> n;
for (int i = 1; i <= n; ++ i) {
    z[i][n + (i - 1) * 9 + 1] = 1;
    for (int j = 1; j < 9; ++ j) {
        z[n + (i - 1) * 9 + j][n + (i - 1) * 9 + j + 1] = 1;
    }
}

初等数论

质数（素数）

除 \(1\) 之外，只有 \(1\) 和它本身作为因子的数就是质数。

所有正整数可分为 \(1\)、素数和合数。

判断素数

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

bool is_prime(int x) { // O(sqrt(x))
    if (x < 2)    return false;
    int y = sqrt(x) + 0.5;
    for (int i = 2; i <= sqrt(x); ++ i) {
        if (x % i == 0)    return false;
    }
    return true;
}

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

分解质因数

void factorize(int x) { // 对 x 分解质因数
    for (int a = 2; a * a <= x; ++ a) {
        if (x % a == 0) {
            ++ cnt;
            prime[cnt] = a;
            while (x % a == 0) {
                ++ num[cnt];
                x /= a;
            }
        }
    }
    if (x != 1) {
        ++ cnt;
        prime[cnt] = x;
        num[cnt] = 1;
    }
}

CF45G

有 \(1, 2, 3, 4, 5, \cdots n\)，把这些数分成最少的组，使得每一组的和都是质数。\((n \le 2000)\)

对于任何一个大于等于 \(4\) 的偶数，它一定可以分成 \(2\) 个质数和，任何一个大于等于 \(7\) 的奇数，它一定可以拆成 \(3\) 个质数之和。

算出 \(1 + 2 + 3 + 4 +\cdots + n = x\)

如果 \(x\) 是偶数，那么这时答案是 \(2\)，\(x\) 是奇数，答案小于等于 \(3\)。

当 \(n = 2\) 时，答案为 \(1\)。

如果 \(x - 2\) 是质数，那么答案是 \(2\)。

否则，答案是 \(3\)。

逆元

费马小定理：当 \(p\) 是质数 \((1 \le a < p)\)，\(a^{p} \equiv a \pmod p \Rightarrow a^{p - 1} \bmod p = 1\)

\[a^{p - 1} \equiv 1 \pmod p\\ \Downarrow\\ a^{p - 2} \equiv \dfrac{1}{a} \pmod p\\ \]

费马小定理使用条件：

  1. \(p\) 是质数

  2. \(\gcd(a, p) = 1\)

若 \(p\) 不为质数，但 \(\gcd(a, p) = 1\)，则使用欧拉定理。

欧拉定理：\(a^{\varphi(p)} \equiv 1 \pmod p\)

\(\varphi(p)\)：\(1 - p\) 中有多少个数和 \(p\) 互质。

\(a^{\varphi(p) - 1} \equiv \dfrac{1}{a} \pmod p\)

当 \(p\) 是质数时，\(\varphi(p) = p - 1\)。

当 \(\gcd(a, p) \ne 1\) 时，可以认为不存在逆元。

\(\varphi(n)\) 怎么算？

  1. 枚举 \(1 - n\)，判断是否互质。\(O_{n \log n}\)

  2. \(n\) 是一个质数，\(\varphi(n) = n - 1\)。

  3. \(n = p^2\)，\(\varphi(n) = p^2 - p = p(p - 1)\)

  4. \(n = p^k\)，\(\varphi(n) = \frac{p - 1}{p} \cdot n\)

\[n = p^k, \varphi(n) = \dfrac{p - 1}{p} \cdot n\\ n = p_1p_2, \varphi(n) = n - \dfrac{n}{p_1} - \dfrac{n}{p_2} + \dfrac{n}{p_1p_2}\\ \varphi(n) = n - \dfrac{n}{p_1} - \dfrac{n}{p_2} + \dfrac{n}{p_1p_2} = n(1 - \dfrac{1}{p_1})(1 - \dfrac{1}{p_2}) \]

\[n = p_1^{k_1}p_2^{k_2}\cdots p_t^{k_t}\\ \varphi(n) = n \cdot (1 - \dfrac{1}{p_1})(1 - \dfrac{1}{p_2})\cdots (1 - \dfrac{1}{p_t}) \]

int get_phi(int n) {
    int phi = n;
    for (int i = 2; i * i <= n; ++ i) {
        if (n % i == 0) {
            phi = phi / i * (i - 1);
            while (n % i == 0) {
                n = n / i;
            }
        }
    }
    if (n != 1) {
        phi = phi / n * (n - 1);
    }
    return phi;
}

cin >> n >> p;
// fac[i] = i!
fac[0] = 1;
for (int i = 1; i <= n; ++ i) {
    fac[i] = 1ll * fac[i - 1] * i % p;
}
// ifac[i] = 1 / i! i!的逆元
ifac[n] = ksm(fac[n], p - 2, p);
for (int i = n - 1; i >= 0; i --) {
    ifac[i] = 1ll * ifac[i + 1] * (i + 1) % p;
    // 1/i! = 1/(i + 1)! * (i + 1)
}
// inv[i] = 1 / i i的逆元
// 1 / i = (i - 1)! / i!
for (int i = 1; i <= n; ++ i) {
    inv[i] = 1ll * fac[i - 1] * ifac[i] % p;
}

已知 \(1\) 到 \(n - 1\) 的逆元，求 \(n\) 的逆元。

\[p = ki + r \\ 1 \le r < i\\ 0 \equiv ki + r \pmod p\\ -r \equiv ki \pmod p\\ \dfrac{r}{i} \equiv k \pmod p\\ \dfrac{1}{i} = -\dfrac{k}{r} \pmod p\\ \Downarrow\\ \dfrac{1}{i} \equiv -k \cdot inv_r\\ \]

cin >> n >> p;
inv[1] = 1;
for (int i = 2; i <= n; ++ i) {
    int k = p / i;
    int r = p % i;
    // p = k * i + r
    // 0 = k * i + r (mod p)
    // -r = k * i(mod p)
    // 1 / i = -k / r(mod p)
    inv[i] = 1ll * (p - k) * inv[r] % p;
}

米勒拉宾素性测试

给定 \(n\)，如何判断 \(n\) 是不是质数。

如果 \(n\) 是质数，\(n - 1 = d \times 2^r\)

\(1 \le a < n\)

  1. \(a^d \bmod n = 1\)

  2. 存在 \(0 \le i < r\)，\(a^{d \times 2^i} \bmod n = n - 1\)

若 \(n\) 是质数，则这两条性质至少有一条成立，但是不是质数时这两个性质也可能成立。

如果两个性质都不成立，则一定不是质数。

// n - 1 = d * 2^r
// 找一个 1 <= a < n
// 1. a^d % n = 1
// 2. 存在一个 0 <= i < r，使得 a ^ (d * 2) % n = n - 1
// 当 n 是质数时，两个性质至少一个成立


bool miller_rabin(int n, int a) { // 检查n，a能否满足两个性质中的任意一个
    // log(n)
    int d = n - 1, r = 0;
    while (d % 2 == 0) {
        d = d / 2, ++ r;
    }
    int x = qpow(a, d, n);
    if (x == 1)    return true; // 性质一
    for (int i = 0; i < r; ++ i) { // 性质二
        if (x == n - 1)    return true;
        x = 1ll * x * x % n;
    }
    return false;
}


bool is_prime1(int n) {
    if (n < 2)    return false;
    for (int i = 1; i <= 23; ++ i) {
        int a = rand() % (n - 1) + 1;
        if (!miller_rabin(n, a))    return false;
    }
    return true;
}

int prime_list[] = {2, 3, 5, 7, 13, 23, 37, 73};

bool is_prime2(int n) {
    if (n < 2)    return false;
    for (int i = 0; i < 8; ++ i) {
        if (n == prime_list[i])    return true;
        if (n % prime_list[i] == 0)    return false;
        if (!miller_rabin(n, prime_list[i] % n))    return false;
    }
    return true;
}

不定方程

解方程 \(xa + yb = g\)。\((\gcd(a, b) = g)\)

\[\begin{aligned} &\gcd(a, b)\\ &\quad \Downarrow\\ &\gcd(b, a \bmod b) \Rightarrow x'b + y'(a \bmod b) = g \end{aligned} \]

\[x'b + y'(a \bmod b) = g \Rightarrow xa + yb = g\\ x'b + y'(a - b \cdot \left \lfloor \dfrac{a}{b} \right \rfloor) = g\\ x'b + y'a - y'b \left \lfloor \dfrac{a}{b} \right \rfloor = g\\ y'a + (x' - y' \left \lfloor \dfrac{a}{b} \right \rfloor)b = g\\ x = y', y = (x' - y' \left \lfloor \dfrac{a}{b} \right \rfloor)\\ \]

int exgcd(int a, int b, int &x, int &y) {
    // 求 g = gcd(a, b)
    // 以及 xa + yb = g
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int xp, yp;
    int g = exgcd(b, a % b, xp, yp);
    // xp * b + yp * (a % b) = g
    // xp * b + yp * (a - b * (a  /b)) = g
    // xp * b + yp * a - yp * b * (a / b) = g
    // yp * a + (xp - yp * (a / b)) * b = g
    x = yp, y = xp - yp * (a / b);
    return g;
}

\(xa + yb\)，\(x, y\) 是整数，求 \(x, y\) 能够表示出来的最小正整数。

答案：\(\gcd(a, b)\)

裴属定理。

\(xa + yb = z\)，只有当 \(z \bmod \gcd(a, b) = 0\) 时才有解。

同余方程

\[ax \equiv 1 \pmod b\\ ax = yb + 1\\ ax - yb = 1\\ \]

\[ax + by = g\\ a(x_0 + n) + b(y_0 - m) = g\\ an = bm\\ \dfrac{n}{b} = \dfrac{m}{a}\\ \begin{cases} x = x_0 + \dfrac{b}{g}k\\ y = y_0 - \dfrac{a}{g}k\\ \end{cases} \]

\[2x + 3y = 1\\ \begin{cases} x = 2\\ y = -1\\ \end{cases}\\ x \rightarrow 2 + n\\ y \rightarrow -1 - m\\ 2(2 + n) + 3(-1 - m) = 1\\ 2n = 3m \rightarrow \dfrac{n}{3} = \dfrac{m}{2}\\ \begin{cases} x = 2 + 3k\\ y = -1 - 2k\\ \end{cases} \]

中国剩余定理

\[\begin{cases} x \bmod p_1 = a_1\\ x \bmod p_2 = a_2\\ \cdots\\ x \bmod p_n = a_n\\ \end{cases} \]

\[\begin{cases} x \bmod p_1 = a_1 \rightarrow x = k_1p_1 + a_1\\ x \bmod p_2 = a_2 \rightarrow x = k_2p_2 + a_2\\ \cdots\\ x \bmod p_n = a_n\\ \end{cases} \]

\[\begin{cases} x \bmod 3 = 1\\ x \bmod 5 = 1\\ \end{cases} \]

最小的 \(x\) 为 \(1\)。

\[(1 + k) \bmod 3 = 1 \rightarrow k \bmod 3 = 0\\ (1 + k) \bmod 5 = 1 \rightarrow k \bmod 5 = 0\\ x = 1 + 15k \rightarrow x \bmod 15 = 1\\ \]

\[\begin{cases} x \bmod p_1 = a_1\\ x \bmod p_2 = a_2 \end{cases} \Rightarrow x = a_1 + p_1 \]

void solve(int p1, int a1, int p2, int a2, int &p, int &a) { // 暴力
    // x % p1 = a1
    // x % p2 = a2
    // x % p = a
    // 时间复杂度: O(min(p1, p2))
    if (p1 < p2)    swap(p1, p2), swap(a1, a2);
    int x = a1;
    int g = gcd(p1, p2);
    int l = p1 / g * p2;
    while (x % p2 != a2 && x <= l) {
        x += p1;
    }
    if (x > l)    p = -1, a = -1;
    else    p = l, a = x;
}

\[\begin{cases} x \bmod p_1 = a_1\\ x \bmod p_2 = a_2\\ \end{cases}\\ x = k_1 p_1 + a_1 = k_2 p_2 + a_2\\ k_1 p_1 - k_2 p_2 = a_2 - a_1\\ \Downarrow\\ xa + yb = g\\ \]

void solve(int p1, int a1, int p2, int a2, int &p, int &a) {
// 不要求 p1, p2 互质
// x % p1 = a1
// x % p2 = a2
// x % p = a
// x = k1 * p1 + a1 = k2 * p2 + a2
// k1 * p1 - k2 * p2 = a2 - a1
    int g, k1, k2;
    g = exgcd(p1, p2, k1, k2);
// k1 * p1 + k2 * p2 = g
    k2 = -k2;
// k1 * p1 - k2 * p2 = g
    if ((a2 - a1) % g != 0) {
        p = -1, a = -1;
    }
    else {
        int k = (a2 - a1) / g;
        k1 = k1 * k, k2 = k2 * k;
        // k1 * p1 - k2 * p2 = a2 - a1
        int x = k1 * p1 + a1;
        p = p1 / g * p2;
        a = (x % p + p) % p;
    }
}

筛法

给定一个整数 \(n\)，希望在尽量短的时间内把 \(\left [ 1, n \right]\) 的质数找出来。

  1. \(O_{n \sqrt{n}}\)

  2. Miller-Rabin \(O_{n \log n}\)

  3. \(O_{\frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n} \approx n (\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n}) \approx n \log n}\)

for (int a = 2; a <= n; ++ a) {
    for (int b = a + a; b <= n; b += a) {
        not_prime[b] = true;
    }
}
for (int a = 2; a <= n; ++ a) {
    if (not_prime[a] == false) {
        prime[++ cnt] = a;
    }
}

优化 \(O_{n \log \log n}\)

for (int a = 2; a <= n; ++ a) {
    if (not_prime[a] == false) {
        for (int b = a + a; b <= n; b += a) {
            not_prime[b] = true;
        }
    }
}

线性筛

让每个数被它最小的质因子筛掉。\(O_n\)

for (int i = 2; i <= n; ++ i) {
    if (not_prime[i] == false) {
        prime[++ cnt] = i;
    }
    for (int j = 1; j <= cnt; ++ j) {
        int x = prime[j] * i; // 筛掉第 j 个质数的 i 倍 
        if (x > n)    break;
        not_prime[x] = true;
        if (i % prime[j] == 0)    break;
        // y = prime[j + 1] * i
        // i = prime[j] * k
        // y = prime[j + 1] * prime[j] * k
    }
}

\(10^6\) bool \(\approx 1M\)

\(10 ^ 6\) int \(\approx 4M\)

P3383

欧拉筛求积性函数的值

积性函数：当 \(\gcd(a, b) = 1\),\(f(a)f(b) = f(ab)\)

完全积性函数：\(f(a)f(b) = f(ab)\)

\[n = p_1^{k_1} p_2^{k_2} \cdots p_t^{k_t}\\ \varphi(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots(1 - \frac{1}{p_t})\\ m = q_1^{r_1}q_2^{r_2}\cdots q_w^{r_w}\\ \varphi(m) = m(1 - \dfrac{1}{q_1})(1 - \dfrac{1}{q_2})\cdots (1-\dfrac{1}{q_w})\\ mn = p_1^{k_1} p_2^{k_2} \cdots p_t^{k_t} q_1^{r_1} \cdots q_w^{r_w}\\ \varphi(nm) = nm(1 - \dfrac{1}{p_1})(1 - \dfrac{1}{p_2}) \cdots (1 - \dfrac{1}{p_t}) (1 - \dfrac{1}{q_1}) (1 - \dfrac{1}{q_2} \cdots (1 - \dfrac{1}{q_w})\\ \varphi(nm) = \varphi(n)\varphi(m)\\ \]

phi[1] = 1;
for (int i = 2; i <= n; ++ i) {
    if (not_prime[i] == false) {
        prime[++ cnt] = i;
        phi[i] = i - 1;
    }
    for (int j = 1; j <= cnt; ++ j) {
        int x = prime[j] * i; // 筛掉第 j 个质数的 i 倍 
        if (x > n)    break;
        not_prime[x] = true;
        if (i % prime[j] == 0) {
            phi[x] = prime[j] * phi[i];
            break;
        }
    }
}

\[\varphi(n) = n(1 - \dfrac{1}{p_1}) \cdots (1 - \dfrac{1}{p_k})\\ \varphi(i) = i(1 - \dfrac{1}{q_1}) \cdots (1 - \dfrac{1}{q_r})\\ i \cdot p_j = q_1 q_2 \cdots q_k^{t_k + 1} \cdots q_r\\ \varphi(i \cdot p_j) = p_j \cdot i \cdot (1 - \frac{1}{q_1})\cdots (1 - \frac{1}{q_r})\\ \varphi(i \cdot p_j) = p_j \cdot \varphi(i) \]

BSGS 算法

给定三个数 \(a, b, p\)，\(p\) 是质数，解方程 \(a^x \bmod p = b\)。\((a, b, p \le 10^9)\)

暴力

int solve(int a, int b, int p) {
// O(p)
    int v = 1;
    for (int x = 0; x <= p - 2; ++ x) {
        if (v == b)    return x;
        v = 1ll * v * a % p;
    }
    return -1;
}

为什么一定会在 \(1\) 处循环呢？

因为 \(a^{p - 1} \bmod p = 1\)

\[a^{p - 1 + k} \bmod p\\ \begin{aligned} &= a^{p - 1} \cdot a^k \bmod p\\ &= a^k \bmod p \end{aligned} \]

对于该方程，要枚举 \(p - 1\) 个数，那我们将这 \(p - 1\) 个数分组，\(s\) 为每组的大小

\[a_0 \quad a_1 \quad a_2 \cdots \quad a^{s - 1}\\ \Downarrow (\cdot a^s) \Uparrow (\div a^s)\\ a^s \quad a^{s + 1} \quad a^{s + 2} \cdots a^{2s - 1}\\ a^2s \quad a^{2s + 1} \quad a^{2s + 2} \cdots a^{3s - 1}\\ \]

若第 \(2\) 组数中出现了 \(b\)，那么在第 \(1\) 组中，一定出现了 \(b \cdot a^{-s}\)。

#include <set>
using namespace std;

int solve(int a, int b, int p) {
    int s = sqrt(p);
    int v = 1;
    set<int> se;
    for (int i = 0; i < s; ++ i) {
        se.insert(v);
        v = 1ll * v * a % p;
    }
    // O(p / s)
    for (int i = 0; i * s <= p; ++ i) { // 看答案是否在第 i 行里面
        // 要看 b * a (-is) 是否在第 0 行出现
        int c = 1ll * b * qpow(qpow(a, i * s, p), p - 2, p) % p;
        if (se.count(c) != 0) {
            int v = qpow(a, i * s, p); // 第 i 行的第一个数
            for (int j = i * s; ; ++ j) { // O(s)
                if (v == b)    return j;
                v = 1ll * v * a % p;
            }
        }
    }
    return -1;
}

\(O(\frac{p}{s} + s) = O(\max(\frac{p}{s}, s))\)

若取 \(s = \sqrt{p}\)，则为 \(O_{\sqrt{p}}\)

标签：gcd,数论,dfrac,bmod,笔记,学习,int,bmatrix,cdot
From： https://www.cnblogs.com/yifan0305/p/17398926.html

相关文章

  • MarkDown学习
    MarkDown（一级标题）二级标题三级标题四级标题 字体Hello,World（粗体：内容两侧加“**”）Hello，World(斜体：内容两侧加“*”)Hello，World（斜体加粗：内容两侧加“***”）Hello,World(删除：内容两侧加“~~”) 引用选择狂神说Java，走向人生巅峰（内容的前面加“>”） 分割线（分......
  • 小灰灰机器学习day3——多项式拟合(最高项系数为2)
    importnumpyasnpTime=np.array([1,2,4,8,16,32,64])Temp=np.array([0,1,2,3,4,5,6])importmatplotlib.pyplotaspltplt.figure()plt.plot(Time,Temp,'bo')plt.xlabel("Time")plt.ylabel("Temp")plt.title(�......
  • 英语学习
    1.another ,other,theother,theothers,有the指全部,s是复数2.howsoon多久以后 howlong  多长时间3.趋向动词的ing就可以表达将来的含义  beleaving表示将要离开,其实也是瞬间动词,也就是瞬间动词+ing表示将来的意味趋向动词:go,come,leave,arrive,st......
  • FFT学习笔记
    fft.1单位根的性质\[1.w^{dk}_{dN}=w^k_N\]\[2.\frac{1}{\omega_k}=\omega_k^{-1}=e^{-\frac{2\pii}{k}}=\cos\left(\frac{2\pi}{k}\right)+i\cdot\sin\left(-\frac{2\pi}{k}\right)\]递归求解\(F[\)\(]\)=\(1\)\(2\)\(3\)\(4\)\(5\)......
  • C#学习笔记 -- 匿名方法、Lambda表达式
    匿名方法前面的情况是方法被某个结构或者类的成员,可以调用方法如果方法只调用一次,用来实例化委托,在这种情况下,除了创建委托的语法需要,没有必要创建独立的具名方法,使用匿名方法即可匿名方法是实例化委托时内联声明的方法.classProgram{  delegatei......
  • python自学笔记
    变量类型：整型int，字符串str，浮点型float；算术运算：+、-、*、/、%、**（乘方）、//（整除）；逻辑运算：not、and、or；布尔类型：True、False；比较运算：>、>=、<、<=、==、!=；变量命名规则：字母+数字+下划线、区分大小写、数字不开头、不能用空格、不能用保留字；输入input（）、输出print（）；字符串拼接：prin......
  • html 学习笔记
    目录基础知识斜体强调行内容着重强调空元素插入图片的示例添加超链接属性布尔属性禁用表单输入剖析HTML文档头(head)在搜索引擎中description的使用在头里引用CSS文件在头里引用JavaScript文件创建超链接使用title属性添加支持信息这里有统一资源定位符（URL）与路径（path）快速入......
  • 数学巧思笔记(证明+概念组合)
    利用夹逼准则+三角函数公式，求证$\lim\limits_{x\to0}\frac{sinx→三角形}{x→角度}=1$......
  • 读书笔记
    读书笔记种树最好的时间是十年前，其次是现在简介：我决定从今天开始记录我读书的过程（也可能是从几天前），记录我读的书，书的相关信息，我的读书方法，一些好句，我的心得。三分读书法：这是我从up主阿鱼爱学习本人学来的技巧，我认为这是一种很好的读书笔记的形式，能让我们在阅读时保持清......
  • CSS笔记
    概述简介：用于设置文本内容，图片外形，版面的布局和外观显示样式。组成：css由选择器及声明两个重要部分组成语法：选择器{声明}，声明为键值对形式，选择器分为基础选择器复合选择器引入方式：行内样式表（行内式）：在标签内部的style属性中设定css样式内部样式表（嵌入......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99