数论相关

扩展欧几里得算法

基础

欧几里得算法可以用于求 $a,b$ 的最大公因数：

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

扩展欧几里得算法可以用于求方程 $ax+by=gcd(a,b)$ 的一组整数解 $x,y$ 。

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

二元一次方程

求特解

根据翡蜀定理，类似于 $ax+by=gcd(a,b)$ 的方程必定有整数解。

推广到一般情况: $ax+by=c$ 这样的普通二元一次方程方程也可以用exgcd求解。

定义 $t = gcd(a,b)$ ，如果 $c|t$ 则有解，反之无解。

如果有解，定义 $k = \frac{c}{t}$ ,将 $c$ 除以 $k$ 得一个新方程 $ax+by=t=gcd(a,b)$ 。

这个新方程可以使用exgcd解出一组特解 $x_0,y_0$ 。因为新方程由原方程的 $c$ 除以 $k$ 得到，所以原方程的特解 $\begin{cases}x_1&=x_0 \times k\\ y_1&=y_0 \times k\end{cases}$

如果你想要的是x的最小正整数解(使 $x$ 最小)，那么你可能需要对 $x_1,y_1$ 做一些处理。

$\begin{cases}x_1 &= (x_1 \bmod b + b) \bmod b \\y_1 &= \frac{c-ax_1}{b}\end{cases}$

方便起见，后文的 $x_1,y_1$ 都指这里的最小正整数解。

exgcd找到的不一定是最小正整数解(事实上，它甚至有可能不是正整数)，但一定是整数解。

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1,y = 0;
        return a;
    }
    int t = exgcd(b,a%b,y,x);
    y -= a / b * x;
    return t;
}
inline bool linear_equation(int a,int b,int c,int &x,int &y){//得到二元一次方程 ax+by=c的解
    int t = exgcd(a,b,x,y);//直接求出ax+by=gcd(a,b)=t的解，这样只需要跑一遍exgcd，不用先跑一遍gcd验证答案
    if(c%t!=0)  return false;//无整数解
    int k = c / t;
    x *= k,y *= k;//得到原方程的解
    x = (x % b + b) % b;//得到最小正整数解
    y = (c - ax) / b;
    return true;//有整数解
}   

求通解

手玩一下方程 $4x + 2y = 16$ ，可以找到以下的正整数解。

i	1	2	3
x	1	2	3
y	6	4	2

发现对于方程 $ax+by=c$ ，把 x+=b/gcd(a,b),y-=a/gcd(a,b)，便可以得到另一组解。

得到通解公式:

$\begin{cases} x&=x_0+m \times \frac{b}{gcd(a,b)}\\ y&=y_0-m \times \frac{a}{gcd(a,b)} \end{cases}$

$m$ 为任意整数。

很显然， $x$ 越大 $y$ 越小(因为 $ax+by$ 的和恒定)。

这在求 $x,y$ 的最大/最小值时非常有用。

正整数解的数量

得出了通解公式后就可以得出正整数解的数量。显然，当 $x$ 为最小正整数值时， $y$ 为最大正整数值。

$\lfloor \frac{-x1+1}{\frac{b}{gcd(a,b)}} \rfloor \leq m \leq \lfloor \frac{y_1-1}{\frac{a}{gcd(a,b)}} \rfloor$

直接算出 $m$ 的整数值数量即可。

只有正整数解的数量，没有整数解的数量。

二元不定方程整数解是无限多的。

线性同余方程

每一节的相同字母的意义不一定一样！

类似于 $ax \equiv b \pmod m$ 的方程被称为线性同余方程。

原方程可以变换为 $ax = my + b$ 即 $ax - my = b$ 。

然后把 $m$ 取相反数，就得到 $ax+my=b$ 。

直接使用上一节提到的exgcd解二元一次方程的方法就可以解出了。

别忘了把 $y$ 取反！

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1,y = 0;
        return a;
    }
    int t = exgcd(b,a%b,y,x);
    y -= a / b * x;
    return t;
}
int congruence_equation(int a,int b,int m){
    int x,y,g=exgcd(a,m,x,y);
    if(b%g!=0)  return -114514;//无解
    return (x%m+m)%m;//转为最小正整数解
}

逆元

众所周知，取模运算不影响加法，减法，乘法的结果，但是影响除法的结果。

所以如果题目需要你取模的式子中有除法，就需要使用逆元。

定义

如果 $ax \equiv 1 \pmod m$ ，则 $x$ 称为 $a \bmod b$ 的逆元，记作 $a^{-1}$ 。

求逆元

求逆元的方法有exgcd法，快速幂(费马小定理)法等。这里主要讲解exgcd法。

求解逆元与求解线性同余方程是同一个原理。

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