取模

$(a+b) \bmod p=(a\bmod p+b\bmod p)\bmod p$ $(a-b) \bmod p=(a\bmod p-b\bmod p+p)\bmod p$ $(a\times b) \bmod p=(a\bmod p\times b\bmod p)\bmod p$

求$\dfrac{a}{b}\bmod p$时,求$b^{-1}$使$b*b^{-1}\equiv1\pmod p$即$b$的逆元

有 $\dfrac{a}{b}\bmod p=a\times b^{-1}\bmod p$

费马小定理

定理：当$p$是质数时$a^{p-1}\equiv 1\pmod p$

逆元：由$a^{p-1}\equiv 1\pmod p$得$a\times a^{p-2}\equiv 1\pmod p$

即$a^{p-2}$是$a$在模$p$意义下的逆元

欧拉定理

若$gcd(a,p)=1$则$a^{\varphi(p)}\equiv1\pmod n$

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

即$a^{p-1}\equiv1\pmod n$即费马小定理

GCD EXGCD

#define ll long long
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
void exgcd(ll a, ll b, ll &x, ll &y) {
    if(!b) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}

$gcd$用来求解$a，b$的最大公约数

$lcm(a,b)=\dfrac{a\times b}{gcd(a,b)}$，lcm是最大公约数

$exgcd$用来求解$ax+by=gcd(a,b)$，证明大概是化式子构造递归的解法，反正看了也早晚会忘就是了逃

$exgcd$还可以求解$ax\equiv b\pmod p$形式的同余方程

$exgcd(a,p,x,y)$求出来的$x$就是$a$关于$p$的逆元

CRT exCRT

求解一个同余方程组

$\begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ x \equiv a_n \pmod {m_n} \end{cases}$

两种东西都可以通过exgcd两两合并同余方程求解，不过CRT可以直接构造出答案。

CRT求解的$p$是质数，exCRT的不是，都可以用exgcd合并做。

推导参考这个blog：扩展欧几里得算法与中国剩余定理

CRT直接构造的解：

令$M=\prod m_i, M_i=\frac M{m_i}$，$t_i$为$M_i$在模$m_i$意义下的逆元

方程组的解为 $x \equiv \sum_{i=1}^na_it_iM_i \pmod M$

筛法

求$n$是不是素数直接枚举$1$到$\sqrt{n}$试除

埃筛

for(int i = 2; i <= N; i++) if(!vis[i]) {
    prime[++cnt] = i;
    for(int j = 1; i * j <= N; j++)
           vis[i * j] = 1;
}

线筛

for(int i = 2; i <= N; i++) {
    if(!vis[i]) prime[++cnt] = i;
    for(int j = 1; j <= cnt && i * prime[j] <= N; j++) {
        vis[i * prime[j]] = 1;
        if(i % prime[j] == 0) break;
    }
}

本文由落影汐雾原创，采用保留署名-非商业性使用-禁止演绎 4.0-国际许可协议
本文链接：https://x.lyxw.xyz/2019/number_theory/