裴蜀定理

上一篇提到过，\(ax+by=c\)有解，当且仅当\(c=m*gcd(a,b)\) (m为正整数)

所以当\(gcd(a,b)=1\)时，c可以取任意数

线性同余方程

推导

形如 \(ax \equiv c \pmod b\) 的东西叫线性同余方程 (Congruence Equation)

怎么解？

这不就相当于 \((ax-c)\%b==0\)，即\((ax-c)\)为\(b\)倍数吗！

设它为 \(-y\) 倍，这样不就有 \((ax-c)=-by\)，就是 \(ax+by=c\) 了吗！（所以为什么要设为-y倍就是如此——让化简后式子精简）

然后这不就一个exgcd搞定了吗！做完了！Time: \(O(logn)\)

例题

**同余方程，一句话题意：给 \(a\)、\(b\) 值，求 \(a x \equiv 1 \pmod b\) 合法的 \(x\)

#include<bits/stdc++.h>
using namespace std;
int a,b,xx,yy;

void exgcd(int p,int q,int &x,int &y){
	if(!q){x=1,y=0;return;}
	exgcd(q,p%q,x,y);
	int tmp=x;
	x=y,y=tmp-(p/q)*y;
}

int main(){
	cin>>a>>b;
	exgcd(a,b,xx,yy);
	while(xx<=0)xx+=b;
	cout<<xx%b;
}

---

中国剩余定理

给定\(a_i,n_i\)（所有n两两互质），求x的可行解。方程组如下：

\(\left\{\begin{array}{l} x \equiv a_{1}\left(\bmod n_{1}\right) \\ x \equiv a_{2}\left(\bmod n_{2}\right) \\ \vdots \\ x \equiv a_{k}\left(\bmod n_{k}\right) \end{array}\right.\)

怎么求呢？（下面两行是精简版，不理解可以直接跳至第三行）

一句话 \(\Large{x=\sum_{i=1}^{k}a_i*\frac {\prod_{j=1}^n n_{_j}}{n_{_i}}*inv[\,\frac {\prod_{j=1}^n n_{_j}}{n_{_i}}\,]}\)（啊这）

其中\(inv[x]\)如果它的分母是\(n_i\)则表示整个式子模\(\prod_{i=1}^kn_k\)下的逆元

• 具体来说，首先计算 \(n=\prod_{i=1}^n n_i\)。

  然后对于每个式子 \(m_i=\frac{n}{n_i}\)，并计算其在 模\(n_i\)意义 下的逆元 \(m_i^{-1}\)。接下来计算\(c_i=m_im_i^{-1}\) （\(c_i\)不要取模）

  最后 \(x=\sum_{i=1}^{-1}a_ic_i(mod\,\,n)\)

Time: \(O(k)\)，k是式子的数量

证明：不知道。