数论公式_牛客博客

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

整除与不定方程

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

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

$(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,\\y = y_0-\frac{a}{(a,b)}t$ $

同余理论

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

$a \equiv b (\mod m) \Leftrightarrow (a-b)|m$
$a \equiv b (\mod m),a \equiv b (\mod n) \Leftrightarrow a \equiv b (\mod [n,m])$
$g = (k,m),ka \equiv ka' (\mod m) \Leftrightarrow a \equiv a'(\mod \frac{m}{g})$
证明都是转成整除来证。
求解 $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$ 的。

求解线性同余方程组（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;
}

欧拉函数

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

$\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}$

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

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

$\varphi(n) = n\Pi \frac{p-1}{p}$
证明：质因数分解就可以了。
$\varphi(p) = varphi(\frac{n}{p})*p (p|\frac{n}{p})$
按照 $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)$ $
$a (\mod m)$ 的阶
如果 $(a,m) = 1$ ，那么记 $x$ 为最小的正整数使得 $a^x \equiv 1(\mod m)$ 为阶。
简单的小性质是 $x | \varphi(m)$ 。
证明：反证法，欧拉定理。
所以求阶的时候可以试除 $\varphi(m)$ 的质因子。
逆元
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}$

数论公式

整除与不定方程

同余理论

欧拉函数

逆元