数论杂谈 - zerc

众所周知，OI 中的数学不需要证明（最起码大部分是这样的，

所以，这篇博客只保留部分必要的证明。

壹·素数相关

判定

bool judge(int x) {
    if (x < 2) return 0;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return 0;
   return 1;
}

筛法

Eratosthenes 筛

对于一个大于 $1$ 的正整数 $n$ 他的倍数 $kn$ 一定是合数（$k>1$）。Eratosthenes 筛利用这样的思想，对每一个质数的倍数进行标记，没有被标记的数就是质数。

时间复杂度 $O(n\log\log n)$，需要注意的是使用 bitset 代替 bool 数组，在吸氧的情况下可以获得更好的常数优势，不开 $O_2$ 慎用。

bitset<maxn> vis; 
void GetPrimes () {
    for (int i = 2; i * i <= n; i++) {
        if (vis[i]) continue;
        prime[++cnt] = i;
        for (int j = i; j <= n / i; j++)
            vis[i * j] = 1;
    }
}

Euler 筛

如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 $O(n)$ 了。

int vis[maxn], prime[maxn];
void GetPrimes () {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) 
            vis[i] = i, prime[++cnt] = i;
        for (int j = 1; j <= cnt; j++) {
            if (prime[j] > vis[i] || prime[j] > n / i)
                break;
            vis[i * prime[j]] = prime[j];
        }
    }
}

筛法求数论函数

咕咕咕···

贰·基本定理

唯一分解定理

$$\begin{aligned} a = \prod_{1 \le i \le m} p_i^{c_i} \end{aligned}$$

裴蜀定理

设 $a,b$ 是不全为零的整数，则存在整数 $x,y$, 使得 $ax+by=\gcd(a,b)$.

Euler 定理 & 费马小定理

费马小定理

$p\in primes$ 则 $a^{p-1}\equiv1(\bmod p)$

Euler 定理

$\gcd(a,m)=1$ 则 $a^{\varphi(m)}\equiv1(\bmod m)$

扩展 Euler 定理

$$ a^b\equiv\begin{cases}a^{b\bmod\varphi(m)},&\gcd(a,m)=1,\\ a^b,&\gcd(a,m)\ne1,b<\varphi(m),\\ a^{(b\bmod \varphi(m))+\varphi(m)},&\gcd(a,m)\ne1,b\ge\varphi(m).\end{cases}\pmod m$$

中国剩余定理

Wilson 定理

$(p-1)!\equiv1(\bmod p)$

用处：化简式子。

Lucas 定理

拉格朗日定理

叁·同余相关

乘法逆元

对于线性同余方程 $ax\equiv 1(\bmod b)$，则 $x$ 为 $a \bmod b$ 的逆元，记作 $a^{-1}$

扩欧求逆

要求：$a \perp p$

void ExGcd (int a, int b, int &x, int &y) {
    if (!b) x = 1, y = 0;
    else ExGcd (b, a % b, y, x), y -= a / b * x;
}

x = (x % p + p) % p;

快速幂求逆

要求：$p \in primes$

llt Pow(llt a, llt b) {
    llt res = 1;
    for ( ; b; b >>= 1, a = a * a % p)
        if (b & 1) res = res * a % p;
       return res;
}

x = Pow(a, p - 2);

线性求逆

证明略过。

inv[1] = 1;
for (int i = 1; i <= n; i++)
    inv[i] = 1ll * (p - p / i) * inv[p % i] % p;

最常用到的还是线性求阶乘的逆：

void init(int n) {
    fac[0] = 1;
    for (i = 1; i <= n; i++)
        fac[i] = 1ll * fac[i-1] * i % mod;
    inv[n] = Pow(fac[n], mod - 2, mod);
    for (i = n; i >= 1; i--)
        inv[i-1] = 1ll * inv[i] * i % mod;
}

线性求任意 n 个数的逆元

没用过，就不写了。

肆·基本算法

GCD 相关

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

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