记录各种我这种数论菜鸡不会的式子。。。可能有很 zz 的式子大佬不要嘲笑

<h3>整除与不定方程</h3>

1. $d|a,d|b \Leftrightarrow d|(a-b)$

证明：$a = pd,b = qd,a-b = (p-q)d$

1. $(a,b)|d \Leftrightarrow ax+by = d$ 存在整数解。

证明：
从右往左推：令 $g=(a,b)$,则有 $g|ua,g|vb \Rightarrow g|(ua+vb) \Rightarrow g|d$
从左往右推：考虑构造 $ax+by = (a,b)$，这样就可以构造出 $(a,b)|d$ 所有 $d$ 的解了。
令$a' = \frac{a}{g},b' = \frac{b}{g}$,证明 $a'x+b'y = 1$
现在我们尝试解 $ax+by = 1$
显然 $(a,b) = 1$,考虑设 $a>0$。
如果 $bx+(a\mod b)y = 1$有解即可。递归出口是 $a = 1,b = 0$,显然有解。
现在考虑如何从递归结果得到解：
$bx+(a\mod b)y = bx+(a-\lfloor\frac{a}{b}\rfloor b)y = bx+ay-\lfloor\frac{a}{b}\rfloor by = ay+b(x-\lfloor\frac{a}{b}\rfloor y)$
所以 $x' = y,y' = x-\lfloor\frac{a}{b}\rfloor y$。
递归下去求解的方法 叫做扩展欧几里得。递归过程中可以顺便处理出 gcd。

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

对于一般的不定方程 $ax+by=c$ 的求解，首先判断是否有 $(a,b)|c$，不满足就无整数解。否则我们令 $g = (a,b)$ 先求出 $ax+by = g$ 的解。然后解乘上 $\frac{c}{g}$ 即可。
对于一般的不定方程，如果有一组特解 $(x_0,y_0)$，通解可以表示成 $$x = x_0+\frac{b}{(a,b)}t,&#92;\ y = y_0-\frac{a}{(a,b)}t$$

<h3>同余理论</h3>

如果 $a \mod p = b \mod m$，我们可以简记为 $a \equiv b (\mod m)$

1. $a \equiv b (\mod m) \Leftrightarrow (a-b)|m$
2. $a \equiv b (\mod m),a \equiv b (\mod n) \Leftrightarrow a \equiv b (\mod [n,m])$
3. $g = (k,m),ka \equiv ka' (\mod m) \Leftrightarrow a \equiv a'(\mod \frac{m}{g})$
   证明都是转成整除来证。

4. 求解 $ax \equiv b(\mod m)$

方法一：
$ax\equiv b(\mod m) \Rightarrow (ax-b)|m \Rightarrow my = ax-b \Rightarrow ax-my = b$
用 exgcd 求解即可。
方法二：
一开始我们确定两个同余方程：
$mx \equiv 0(\mod m)$
$ax \equiv b(\mod m)$
左右系数不断辗转相除，左边会变成 $(m,a)$,右边会变成 $b'$
然后 $\frac{b'}{(m,a)}$ 就是答案。 每次辗转相除是要减去 $\lfloor \frac{m}{a} \rfloor$ 的。

1. 求解线性同余方程组（exCRT）
   首先我们考虑过程中的两个方程

$$x \equiv a(\mod b) \tag 1$$$$ x\equiv c(\mod d) \tag 2$$
$(1)$式可以得到 $x = a+bt$，代入 $(2)$ 得到
$$bt \equiv c-a(\mod d)$$
解一下这个 $t$，带回原式找到 $x_0$，合并成新方程
$$x \equiv x_0 (\mod [b,d])$$
代码：

inline int excrt(){
    int ans = aa[1],M = bb[1];// M = lcm
    FOR(i,2,n){
        int a = M,b = bb[i],c = (aa[i]-ans%b+b)%b;// 这里 ax=c(mod b)
        int g = exgcd(a,b,x,y),bg = b/g;
        if(c%g) return -1;
        x = qmul(x,c/g,bg);
        ans = ans+M*x;
        M *= bg;
        ans = (ans+M)%M; // 这里已经是新意义下的了
    }
    return (ans+M)%M;
}

<h3>欧拉函数</h3>

简化剩余系：1~n 中与 $n$ 互质的数，记 $\varphi(n)$ 表示数的个数。

1. $\varphi(p^e) = (p-1)p^{e-1}$

考虑不与其互质的数一定是形如 $p* 1,p* 2,\cdots,p* p^{e-1}$，所以有 $p^{e-1}$个。
$\varphi(p^{e}) = p^e-p^{e-1} = (p-1)p^{e-1}$

1. $(a,b) = 1,\varphi(ab) = \varphi(a)\varphi(b)$

积性函数。这里不详细证明。

1. $\varphi(n) = n\Pi \frac{p-1}{p}$
   证明：质因数分解就可以了。
2. $\varphi(p) = varphi(\frac{n}{p})* p (p|\frac{n}{p})$
   按照 $3$ 的式子观察一下就好了。
3. $(a,m) = 1 \Rightarrow a^{\varphi(m)} = 1(\mod m)$
   证明：设 $x$ 取遍模 $m$ 意义下的缩系$(p_1,p_2,\cdots,p_n)$，那么 $ax$ 也取遍模 $m$ 意义下的缩系 $(ap_1,ap_2,\cdots,ap_n)$，(因为互不相同且互质，可以使用反证法)。所以 $$\Pi_{i=1}^n ax_i \equiv \Pi_{i=1}^n x_i (\mod m)\Rightarrow a^{\varphi(m)} \equiv 1 (\mod m)$$
4. $a (\mod m)$ 的阶
   如果 $(a,m) = 1$，那么记 $x$ 为最小的正整数使得 $a^x \equiv 1(\mod m)$为阶。

简单的小性质是 $x | \varphi(m)$。
证明：反证法，欧拉定理。
所以求阶的时候可以试除 $\varphi(m)$ 的质因子。

<h3>逆元</h3>

LOJ161：求 $a_1,a_2,\cdots,a_n$ 在模 $p$ 意义下的逆元，$p \leq 10^9$级别。
做前缀积 $pre_i$，前缀逆元积 $ipre_i = ipre_{i+1}* a_{i+1}$
那么逆元 $inv_i = ipre_i* pre_{i-1}$