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;
    //先判无解,如果有解就模
}

原文地址:http://www.cnblogs.com/caijianhong/p/template-exgcd.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性