首页 > 其他分享 >【模板】二元一次不定方程 exgcd

【模板】二元一次不定方程 exgcd

时间:2022-11-06 19:37:24浏览次数:81  
标签:return gcd cdot LL exgcd bmod 模板 二元

posted on 2022-09-17 15:59:26 | under 模板 | source

code

LL mod(LL x,LL m){return(x%m+m)%m;}
LL exgcd(LL a,LL b,LL c,LL& x,LL& y){
	if(!b) return x=c/a,y=0,a;
	LL res=exgcd(b,a%b,c,y,x);
	return y-=a/b*x,res;
}
LL solve(LL a,LL b,LL c){
	LL x,y,d=exgcd(a,b,c,x,y);
	return c%d==0?mod(x,b/d):-1;
}

调用 solve(a,b,c) 能求得 \(ax+by=c\) 中 \(x\) 的最小正整数解,无解返回 \(-1\)。

但是,为什么这样写对呢?

exgcd

我们想求的是这样一个东西的一组解 \((x,y)\):\(ax+by=\gcd(a,b)\)。

回忆一下我们求 \(\gcd\) 的过程,我们用到了 \(\gcd(a,b)=\gcd(b,a\bmod b)\) 的性质。

将原方程的 \((a,b)\) 全部替换成 \((b,a\bmod b)\) 也应该成立:

\[bx+(a\bmod b)y=\gcd(b,a\bmod b). \]

取模的定义:\(a\bmod b=a-\left\lfloor\frac{a}{b}\right\rfloor\cdot b\)(下文 \(\left\lfloor\frac{a}{b}\right\rfloor\) 写作 \(a/b\)),代入:

\[\begin{aligned} bx+(a-(a/b)\cdot b)y&=\gcd(b,a\bmod b)\\ bx+ay-(a/b)\cdot by&=\gcd(b,a\bmod b)\\ ay+b(x-(a/b)\cdot y)&=\gcd(b,a\bmod b)\\ \end{aligned}\]

我们貌似看到了一组新的解 \((x'=y,y'=x-(a/b)\cdot y)\)。这就是 exgcd。将这个过程递归下去即可。

发现还有递归边界,此时 \(b=0\),原方程变为 \(ax=a\)(\(a\) 是原来的 \(\gcd(a,b)\)),取 \((x=1,y=0)\)(\(y\) 可以是任何数,但一般取 \(0\)),即为递归边界。

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

analysis

exgcd 可以求出形如 \(ax+by=\gcd(a,b)\) 的一组整数特解 \((x_0,y_0)\)。

由裴蜀定理得,如果 \(\gcd(a,b)\not|c\) 那么直接跑路。

否则,等式两边同时乘 \(\frac{c}{\gcd(a,b)}\),得到原方程 \(ax+by=c\) 的特解 \((x_1=\frac{c}{\gcd(a,b)}\cdot x_0,y_1=\frac{c}{\gcd(a,b)}\cdot y_0)\)。

考虑这么一个式子,它和原方程等价:

\[a(x_1+db)+b(y_1-da)=c. \]

显然 \(d\) 可以取到 \(\gcd(a,b)^{-1}\),所以得到任意一组解 \((x,y)\) 都满足:

\[\begin{cases} x=x_1+s\cdot\frac{b}{\gcd(a,b)},\\ y=y_1-s\cdot\frac{a}{\gcd(a,b)}.\\ \end{cases}\]

所以 \(x\) 的最小的正整数解是 \(x_0\bmod \frac{b}{\gcd(a,b)}\)。我们止步于此。

code-analysis

LL mod(LL x,LL m){return(x%m+m)%m;}
LL exgcd(LL a,LL b,LL c,LL& x,LL& y){
	if(!b) return x=c/a,y=0,a;
    //x=c/a,提前算好 x_1,这里 a 是 gcd
	LL res=exgcd(b,a%b,c,y,x);
	return y-=a/b*x,res;
}
LL solve(LL a,LL b,LL c){
	LL x,y,d=exgcd(a,b,c,x,y);
	return c%d==0?mod(x,b/d):-1;
    //先判无解,如果有解就模
}

标签:return,gcd,cdot,LL,exgcd,bmod,模板,二元
From: https://www.cnblogs.com/caijianhong/p/16863463.html

相关文章

  • 【模板】二维数点
    postedon2022-10-2313:50:24|under模板|sourceproblem给定一个二维平面,多次询问\(x\in[l_x,r_x],y\in[l_y,r_y]\)的点有多少个。solution1(静态+在线):可持久化......
  • 【模板】网络流
    postedon2022-08-1214:14:05|under模板|source感谢讲师LQS带来的网络流专题。本文非常不严谨,请不要把它当作入门博客。0xFF目录0x00网络流及求法0x01......
  • 【模板】多项式乘法 FFT
    postedon2022-08-0223:57:12|under模板|source涉世不深,不会卡常,恳求大佬指教typedefcomplex<double>comp;constdoublePI=acos(-1);template<intN>struct......
  • 【模板】对拍
    postedon2022-10-1813:30:17|under模板|sourceconstchar*name="bit";#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;type......
  • 【模板】动态树 Link-Cut Tree
    postedon2022-08-1718:05:59|under模板|sourcetemplate<intN>structlctree{ intval[N+10],sum[N+10],fa[N+10],ch[N+10][2],rev[N+10]; boolgetson(intp)......
  • 【模板】点分治 Centroid Decomposition
    postedon2022-07-2018:59:16|under模板|source0x00模板(P3806)给定\(n,k\)和一棵树,计算\[\sum\limits_{i,j\leqn}[{\ttdist}(i,j)=k]\]即树上距离为\(k\)......
  • 【模板】并查集 DSU
    postedon2021-09-1215:49:52|under模板|source0x00模板并查集维护的是这样一个问题:\(n\)个点,初始时每个点自己一个集合。\({\ttmerge}(x,y)\):合并\(x,y\)......
  • 【模板】Z 函数(扩展 KMP)
    postedon2022-08-0823:29:53|under模板|source#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;typedeflonglongLL;intn,......
  • 【模板】Tarjan
    postedon2022-07-0720:52:49|under模板|source0x00有向图缩点现有一有向图\(G=(V,E)\),称一个点集\(E'\inE\)为强连通分量,当且仅当\(E'\)的任意两点可以互......
  • 【模板】ST 表 Sparse Table
    postedon2022-07-2219:15:58|under模板|sourcetemplate<intN,classT=int,intlogN=20>structSTable{ inttot,lg[N+10];Tf[logN+1][N+10]; STable():tot(0......