数学基础

最大公约数

更相减损

$gcd(a,b)=gcd(a-b,b)$

证明：咕咕咕

欧几里得

只需要在更相减损的基础上把减法优化成取模即可：

$gcd(a,b)=gcd(b,a\%b)$

裴蜀定理和exgcd（扩展欧几里得）

首先，有个神奇的东西叫裴蜀等式/裴蜀定理。

这里有一个不定方程：$ax+by=m$。

裴蜀定理就是如果上面这个不定方程有解当且仅当$gcd(a,b)|m$。且当这个不定方程有解时，一定有无数多组解。

证明：（咕咕咕）

对于方程：$ax+by=gcd(a,b)$，我们可以用exgcd算法找到这个式子的一组解，然后就能就能推出$ax+by=m$的解。

而$ax+by=gcd(a,b)$可以通过递归构造解来解决：

\[ a \bmod b=a-\left \lfloor \frac{a}{b} \right \rfloor b \\假设存在x',y'使得x'b+y'(a \bmod b)=d \\则x'b+y'(a-\left \lfloor \frac{a}{b} \right \rfloor b)=d \\把上面这个式子化成ay'+b(x'-y'\left \lfloor \frac{a}{b} \right \rfloor) \\然后我们可以从这一层推出上一层的解x=y',y=(x'-y'\left \lfloor \frac{a}{b} \right \rfloor) \]

特别的，当g欧几里得算法递归到最低一层时，是这个样子的：$gcd(c,d),d=0$

那么对于这种情况我们就可直接得出当前这一层对应的不定方程$cx''+dy''=gcd(c,d)=c$的解：$x''=1,y''=0$然后就可以倒推出上一层的解。

当我们知道一组特解$x0,y0$之后，我们可以推出这个方程的通解：$x=x0+\frac {b}{d}*k,y=y0-\frac {a}{d}*k$其中$d=gcd(a,b)$。至于这个式子是怎么来的，我们可以把式子变成$ax+by+\frac{ab}{d}-\frac{ab}{d}=d$然后提一下公因式就好了。另外，为什么ab要除d而不是其他数字是因为$d=gcd(a,b)$。

至此，我们只求出了$ax+by=gcd(a,b)$的通解。

我们只需要在两边乘上$\frac {m}{gcd(a,b)}$即可，因为这里不变的是系数（x0,y0均乘上这个式子，$a$和$b$不变），所以依旧可以用前面的方法求出特解。

如果遇到求出最小的正整数$x$，我们可以设$p=\frac{b}{d} $，而我们需要的最小正整数x就是:

$(x0\bmod p+p)\bmod p$

代码(引自)：

int exgcd(int a, int b, int &x, int &y) {    if(b == 0) {        x = 1; // 设置b=0时的特殊解         y = 0;        return a;    }    int ans = exgcd(b, a % b, x, y);    int t = x; // 将x2, y2换算成x1, y1    x = y;    y = t - a / b * y;    return ans;}

线性同余方程

形如$ax \equiv c\pmod b$的式子我们称之为一元线性同余方程。

至于这个式子的求解，我们可以先把它化成$ax+by=c$的形式，其中$y<0$。就可以按照不定方程的做法做了。

欧拉函数

欧拉函数的性质

性质1-欧拉定理和扩展欧拉定理

欧拉定理：

当$gcd(a,p)=1$时，

\[ a^{\phi{p}}\equiv1 \pmod p \]

扩展欧拉定理：

\[ a^b\equiv \begin{cases} a^{b\%\phi(p)}~~~~~~~~~~~gcd(a,p)=1\\ a^b~~~~~~~~~~~~~~~~~~gcd(a,p)\neq1,b<\phi(p)\\ a^{b\%\phi(p)+\phi(p)}~~~~gcd(a,p)\neq1,b\geq\phi(p) \end{cases}~~~~~~~(mod~p) \]

性质2-积性函数

$\textrm{当$a,b$互质时 },\phi(a) \times \phi(b)=\phi (ab)$

性质3-欧拉函数特有性质

$\textrm {when $p\mid n$},\phi(np)=\phi(n)*p$

证明：

令$\prod _{p_i\mid np,\textrm { $p_i$ is prime}} (1-\frac{1}{p_i})=A$

$\phi(np)=np*A,\phi (n)=n*A$

显然，$\phi(np)=\phi(n)*p$

得证

当$p$为$n$的一个质因数，$if\ \ p^2|n\ \ then\ \ \varphi(n)=\varphi(\frac{n}{p})*p\ \ else\ \ \varphi(n)=\varphi(\frac{n}{p})*\varphi(p)$

由上一个性质和积性函数性质，很容易可以证明

欧拉函数的求解

咕咕咕

先贴个$O(\sqrt n)$的求欧拉函数板子吧。

代码：

inline int getphi(int x) {    int tmp = sqrt(x), res = x;    for (int i = 1; i <= tmp; i++) {        if (x % i == 0) {            res -= res / i;            while (x % i == 0) x /= i;        }    }    return x > 1 ? res - res / x : res;}

当然，我们也可以用埃氏筛的思路来筛$[1,n]$的欧拉函数。

代码：

inline int getphi(int x){    for(int i=2;i<=x;i++){        if(phi[i])continue;        for(int j=i;j<=x;j+=i){            if(!phi[j])phi[j]=j;            phi[j]=phi[j]/i*(i-1);        }    }    return 0;}