简单数论(扩展欧几里得，同余)（未完成）

梦里梦外; 2023-06-05 08:48 21阅读 0赞

# 扩展欧几里得 #

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

首先我们可以先求出方程\\(ax'+by'=(a,b)\\)的特解。  
\\\[ \\begin\{aligned\} \\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\{aligned\} \\\]  
所以我们就可以得到原方程的一组特解了。那么现在的问题是：如何求出第二个方程的特解呢。

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

接着考虑一般情况：  
\\\[ \\begin\{aligned\} \\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\{aligned\} \\\]

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\\)同余方程(模板)][Rightarrow]

## 逆元 ##

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

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

首先是简单的证明：

假设我们现在要求的是\\(i\\)的逆元,首先  
\\\[ \\begin\{aligned\} &设a=\\lfloor\{M\\over i\}\\rfloor, b=M\\% i\\\\ &\\Rightarrow a\\times i+b\\equiv0\\pmod M\\\\ &\\Rightarrow -a\\times i~~\\equiv b\\pmod M\\\\ &两边同时除以i\\times b\\\\ &可得 -a\\times inv(b)=inv(i)\\pmod M\\\\ &将其转化为一个求inv(i)的表达式:\\\\ &inv(i)=-a\\times inv(b)\\% M\\\\ &\\because -a < 0\\\\ &\\therefore -a\\%M=M-a=M-\\lfloor\{M\\over i\}\\rfloor\\\\ &\\therefore inv(i)=(M-\\lfloor\{M\\over i\}\\rfloor)\\times inv(M\\% i)\\% M\\\\ &特别的，inv(1)=1 \\end\{aligned\} \\\]  
所以代码应该是下面这个样子：

inv[1] = 1;
    for (int i = 2; i <= n; i++)
      inv[i] = (M - M/i) * inv[M%i] % M;

# 中国剩余定理 #

这个暂时不写，我们先来看看扩展中国剩余定理

# EX中国剩余定理 #

和普通的中国剩余定理不同的是，现在每一条方程的模数并不一定是互质的。

我们考虑将两条方程并为一条，做\\(n-1\\)次这样的操作，就可以得到一条最终的方程。

我们考虑有两个方程：  
\\\[ \\begin \{cases\} x\\equiv C\_1\\pmod \{P\_1\}\\\\ x\\equiv C\_2\\pmod \{P\_2\} \\end \{cases\} \\\]  
我们将它们转化为一组不定方程：  
\\\[ \\begin\{cases\} x=C\_1+P\_1y\_1\\\\ x=C\_2+P\_1y\_2 \\end\{cases\} \\\]  
显然我们可以将两条方程的右边用等号连接起来，然后进行变形：  
\\\[ P\_1y\_1-P\_2y\_2=C\_2-C\_1 \\\]  
这个方程有解的条件显然是\\((P\_1, P\_2)| (C\_2-C\_1)\\)

接着我们对这个方程进行变形，然后转化为一个新的同余方程：  
\\\[ \\begin\{aligned\} &\{P\_1\\over (P\_1, P\_2)\}y\_1-\{P\_2\\over (P\_1, P\_2)\}y\_2=\{C\_2-C\_1\\over (P\_1, P\_2)\}\\\\ \\Rightarrow& \{P\_1\\over (P\_1,P\_2)\}y\_1=\{C\_2-C\_1\\over (P\_1, P\_2)\}\\pmod \{ \{P\_2\\over (P\_1, P\_2)\}\} \\end\{aligned\} \\\]  
因为\\(\{P\_1\\over (P\_1, P\_2)\}, \{P\_2\\over (P\_1, P\_2)\}\\)两个数必定互质，所以我们可以在方程两边同时乘上\\(\{P\_1\\over (P\_1, P\_2)\}\\)在模\\(\{P\_2\\over (P\_1, P\_2)\}\\)下的逆元，这里用\\(inv(\{P\_1\\over (P\_1, P\_2)\},\{P\_2\\over (P\_1, P\_2)\})\\)表示。

所以可以得到  
\\\[ \\begin\{aligned\} &y\_1=inv(\{P\_1\\over (P\_1, P\_2)\},\{P\_2\\over (P\_1, P\_2)\})\\times \{C\_2-C\_1\\over (P\_1, P\_2)\}\\%\{P\_2\\over (P\_1, P\_2)\}\\pmod \{ \{P\_2\\over (P\_1, P\_2)\}\}\\\\ \\Rightarrow&y\_1=inv(\{P\_1\\over (P\_1, P\_2)\},\{P\_2\\over (P\_1, P\_2)\})\\times \{C\_2-C\_1\\over (P\_1, P\_2)\}\\%\{P\_2\\over (P\_1, P\_2)\}-\{P\_2\\over (P\_1, P\_2)\}\\times k\\\\ \\because& y\_1=\{C\_1-x\\over P\_1\}\\\\ \\therefore& \{C\_1-x\\over P\_1\}=inv(\{P\_1\\over (P\_1, P\_2)\},\{P\_2\\over (P\_1, P\_2)\})\\times \{C\_2-C\_1\\over (P\_1, P\_2)\}\\%\{P\_2\\over (P\_1, P\_2)\}-\{P\_2\\over (P\_1, P\_2)\}\\times k\\\\ \\Rightarrow& x=inv(\{P\_1\\over (P\_1, P\_2)\},\{P\_2\\over (P\_1, P\_2)\})\\times \{C\_2-C\_1\\over (P\_1, P\_2)\}\\%\{P\_2\\over (P\_1, P\_2)\}\\times P\_1-\{P\_1\\times P\_2\\over (P\_1, P\_2)\}\\times k+C\_1\\\\ \\Rightarrow& x\\equiv inv(\{P\_1\\over (P\_1, P\_2)\},\{P\_2\\over (P\_1, P\_2)\})\\times \{C\_2-C\_1\\over (P\_1, P\_2)\}\\%\{P\_2\\over (P\_1, P\_2)\}\\times P\_1+C\_1\\pmod \{ \{P\_1\\times P\_2\\over (P\_1, P\_2)\}\} \\end\{aligned\} \\\]  
这样之后，我们就把两个方程合为了一个。

而最后的方程中，我们可以取方程右边的值取模，就可以得到最终的答案。

需要注意的是，在编程实现时，因为\\(P\_1\\times P\_2\\)可能会爆掉，所以我们要先做除法在进行乘法运算，另外新方程的右边在这条式子中可能是一个负数，所以我么要再次进行取模。

转载于:https://www.cnblogs.com/juruohjr/p/11314412.html

[Rightarrow]: https://www.luogu.org/problem/P1082