扩展欧几里得

现在有一个不定方程\(ax+by=c\),我们需要求出这个方程的一组特解，且\(x,y\)都为整数。根据悲蜀定理，要得到整数解，必须满足\(\gcd(a,b)|c\),(接下来的所有\(gcd(a,b)\)都会简写为\((a,b)\))

首先我们可以先求出方程\(ax'+by'=(a,b)\)的特解。
\[ \begin{align} \because& c={c\over (a,b)}(a,b)\\ \therefore& a{c\over (a,b)}x'+b{c\over (a,b)}y'={c\over (a,b)}(a,b)\\ \Rightarrow& a{c\over (a,b)}x'+b{c\over (a,b)}y'=c\\ \therefore& x={c\over (a,b)}x', y=b{c\over (a,b)}y' \end{align} \]
所以我们就可以得到原方程的一组特解了。那么现在的问题是：如何求出第二个方程的特解呢。

首先，如果\(b=0\),那么显然可以得到\(a=1, b=0\)。

接着考虑一般情况：
\[ \begin{align} \because& (a,b)=(b, a\% b)\\ \therefore& ax+by=bx'+(a\% b)y'\\ \Rightarrow& ax+by=bx'+(a-\lfloor{a\over b}\rfloor b)y'\\ \Rightarrow& ax+by=ay'+b(x'-\lfloor{a\over b}\rfloor y')\\ \therefore&x=y', y=x'-\lfloor{a\over b}\rfloor y' \end{align} \]

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

同余方程

现在有一个同余方程，形如\(ax\equiv b\pmod p\)，现在需要求出\(x\)。

我们知道同余方程其实可以转化为一个不定方程:\(ax+bp=b\)而这个方程显然可以使用扩展欧几里得进行求解，而有解的条件显然是\((a,p)|b\)

\(\Rightarrow\)同余方程(模板)

逆元

众所周知，模运算之中是不能使用除法的，但是我们知道，除以一个数\(=\)乘上这个数的倒数。那么取模中是否存在类似倒数的东西呢？我们需要知道，假设这个数\(x\)使我们需要的，那它显然要满足\(ax\equiv 1\pmod m\),也就是说\(x\)是\(a\)模\(m\)下的倒数，这个东西也叫作逆元。

这个逆元的求解方法有两种，一种是使用同余方程，一种是线性筛，现在我们就来讲一下线性筛的证明的代码。