数论基础学习笔记

· · 算法·理论

素数

简单知识

定义 \pi(x) 为 [2,x) 中素数的个数。

素数有简单的 O(\sqrt {n}) 的判断方法，这里给出一个 \dfrac{1}{6} 常数的实现：

inline bool isprime(int x) {
    if (x <= 1) return false;
    if (x == 2 || x == 3) return true;
    if (x % 6 != 1 && x % 6 != 5) return false;
    for (int i = 5; i * i <= x; i += 6) {
        if (x % i == 0 || x % (i + 2) == 0) return false;
    }
    return true;
}

原理的话，对于正整数 n，6n+2=2(3n+1),6n+3=3(n+2),6n+4=2(3n+2)，一定不是素数。

算术基本定理

任何一个合数 n 可以唯一分解成有限个质数的乘积。

存在性：用反证法，假设 n 是最小的不能被分解的合数，则存在 n=ab，若 a,b 都可分解，则 n 可以被分解；若 a,b 有不可分解的数，则 a,b 才是最小的数，矛盾。

唯一性：用反证法，假设 n 是最小的存在两种分解的合数，如果 n 存在两种分解 n={p_1}^{a_1} {p_2}^{a_2} \cdots ={q_1}^{b_1} {q_2}^{b_2} \cdots，则 p_1 | {q_1}^{b_1} {q_2}^{b_2} \cdots，也就是 {q_1}^{b_1} {q_2}^{b_2} \cdots 中有一个 {q_i}{b_i} 可以整除 p_1，故 p_1=q_i，同除 p_1，则 {p_2}^{a_2} \cdots 也是存在两种分解的合数，矛盾。

Exgcd

裴蜀定理

对于任意非零整数 a,b，ax+by=c 有整数解当且仅当 c | \gcd(a,b)。

不定方程

由 \gcd(a,b)=\gcd(b,a\bmod b) 得：

ax+by=bx'+(a\bmod b)y'\\ =bx'+(a-b\lfloor \dfrac{a}{b} \rfloor)y'\\ =ay'+b(x'-y'\lfloor \dfrac{a}{b} \rfloor)

递归式：x=y',y=x'-y'\lfloor \dfrac{a}{b} \rfloor，可以 O(\log (a+b)) 求解。

void exgcd(int a, int b, int& x, int& y) {
    if (b == 0) return x = 1, y = 0, void();
    exgcd(b, a % b, x, y);
    int t = x;
    x = y, y = t - a / b * y;
}

乘法逆元

求 x \equiv \dfrac{1}{a} \pmod m 的解。

移项得：ax \equiv 1 \pmod m，即为求解不定方程 ax-bm=1，用 exgcd 求解即可。

欧拉函数

定义 \varphi(x) 为 [1,x] 中与 x 互质的数的个数。

设 x=\prod {x_i}^{p_i}，我们有：

\varphi(x)=\varphi(\prod {x_i}^{p_i})\\ =\prod {x_i}^{p_i}-{x_i}^{p_i-1}\\ =\prod {x_i}^{p_i}\prod (1-\dfrac{1}{p_i})\\ =n\prod (1-\dfrac{1}{p_i})

这样通过分解质因数，可以 O(\sqrt{n}) 地计算欧拉函数。

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

由于欧拉函数是积性函数，可以用线性筛计算。

int n, len, phi[N], prime[N];
bool isprime[N];

inline void eular(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) isprime[i] = true;
    for (int i = 2; i <= n; i++) {
        if (isprime[i]) prime[++len] = i, phi[i] = i - 1;
        for (int j = 1; j <= len && i * prime[j] <= n; j++) {
            isprime[i * prime[j]] = false;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
}

经典定理

费马小定理

当 m 是素数时，

a^{m} \equiv a \pmod m

证明：找到 m 的简化剩余系 S=\{1,2\cdots m-1\}，则 S=aS \bmod n =\{a,2a\cdots (m-1)a\} \bmod n，也就是

\prod_{i=1}^{m-1} i \equiv \prod_{i=1}^{m-1} ia \pmod m

同乘 \prod_{i=1}^{m-1} i 的逆元得

a^{m-1} \equiv 1 \pmod m

也即

a^{m} \equiv a \pmod m

应用：当 m 是质数时，a^{-1}=a^{m-2}，可以简单地求出逆元。

欧拉定理

若 a,m 互质，则

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

证明：找到 m 的简化剩余系 S=\{x_1,x_2\cdots x_n\}，因为 a,m 互质，所以 S=aS \bmod m=\{ax_1,ax_2\cdots ax_n\} \bmod m，即

\prod_{i=1}^{\varphi(m)} i \equiv \prod_{i=1}^{\varphi(m)} ix_i \pmod m

同乘 \prod_{i=1}^{m-1} i 的逆元得

a^{\varphi(m)} \equiv 1\pmod m

Lucas 定理

若 p 为质数，

C_{n}^{m} \equiv C_{\lfloor \frac{n}{p}\rfloor}^{\lfloor \frac{m}{p}\rfloor} \times C_{n \bmod p}^{m \bmod p} \pmod p

这样就可以 O(p \log n) 地快速计算组合数了。

namespace Lucas {
    long long a[N];

    long long power(long long x, int y, int p) {
        long long res = 1; x %= p;
        for (; y; y >>= 1) {
            if (y & 1) res = (res * x) % p;
            x = (x * x) % p;
        }
        return res;
    }

    inline long long cm(long long n, long long m, int p) {
        if (m > n) return 0;
        return (a[n] * power(a[m], p - 2, p)) % p
            * power(a[n - m], p - 2, p) % p;
    }

    inline long long lucas(long long n, long long m, int p) {
        if (m == 0) return 1;
        return cm(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
    }

    inline long long C(int n, int m, int p) {
        a[0] = 1;
        for (int i = 1; i <= p; i++) a[i] = (a[i - 1] * i) % p;
        return lucas(m, n, p);
    }
}