gcd与exgcd
gcd
辗转相除法求gcd证明
\(gcd(a, b) == gcd(b, a\%b)\)
证明:
设: \(d\)为\(a\)与\(b\)的一个公约数, 则有\(d|b\) \(d|a\)
设: \(a = k \times b + r\) 则有\(r = a \% b\)
\(r = a - kb\) 同除以\(d\)可得
\(r\over d\) \(=\) \(a\over d\) \(-\) \(kb\over d\)
又\(\because d|b , d|a\)
\(\therefore d | r\)
即 \(d | a\%b\), \(d\)为\(a\%b\)的一个因数.
又 \(\because d|b\)
\(\therefore d\) 为\(b\)与\(a\%b\)的一个公约数,
若\(d\)最大,则\(d\)为\(b\)与\(a\%b\)的最大公约数,
\(\therefore gcd(a, b) = gcd(b, a \% b)\) 得证
然后就可以递归求解gcd了
exgcd
求出\(a*x+b*y=c\)(a,b,c为常量)的一组解,时间复杂度\(log(a)\)
证明:
\(a*x+b*y=c\) 有整数解的充要条件是\(c\)整除\(gcd(a,b)\)
设\(gcd(a,b)=p\)
1.充分性:
\(a*x+b*y=c\)
\(a'*p*x+b'*p*y=c(a'=a/p)\)
\(p(a'*x+b'*y)=c;\)
因为\(x,y\)必须为整数
所以\(c\)必须整除\(p\)
2.必要性
使用欧几里得和数学归纳法可证明
首先\(b*x_1+(a \% b)*y_1=c\),有整数解,
则\(a*x_2+b*y_2=c\)有整数解
\(a*x_2+b*y_2\)
\(=b*x_1+(a \% b)*y_1\)
\(=b*x_1+(a-\lfloor \frac{a}{b} \rfloor*b)*y_1\)
\(=a*y_1+b*(x_1-\lfloor \frac{a}{b} \rfloor*y_1)\)
然后就可以得到对应关系\(x_2=y_1,y_2=(1-\lfloor \frac{a}{b} \rfloor)*y_1\);
显然最后的\(p,0\)有解
所以求这个\(a*x+b*y=c\)整数解的过程只需要不断递归运行到底层即可
最后一层\(p*x+0*y=c\)的解为\(x=\frac {c}{p},y=0\);
之后再不断用关系\(x_2=y_1,y_2=(x_1-\lfloor \frac{a}{b} \rfloor*y_1)\)推出上一层的解即可
最新文章
- 关于UltraEdit的两个小问题
- #一周五# win10通用平台,无处不在的Xamarin,msbuild开源,MVP卢建晖的Asp.NET 5系列 (视频)
- Sqli-labs less 65
- Microsoft Visual Studio 2013 Update 2 离线安装程序
- c语言中数组相关问题
- servlet过滤器配置白名单、黑名单
- Gentoo本地化设置--时区、时钟、字体、中文环境
- linux通过history查看命令执行时间
- JS中的数据类型小结
- MyEclipse10中配置WebLogic10
- MySQL的安全机制
- persistent_storage_worker.go
- Myeclipse加载php插件
- Laravel 中使用支付宝、银联支付、微信支付进行支付
- LightOJ 1027 A Dangerous Maze(期望)题解
- 创建React组件
- 查看APP的下载量
- C#(少用的)
- 76. Minimum Window Substring(hard 双指针)
- Mysql中与时间相关的统计分析
热门文章
- [转帖]SQL Server DBCC命令大全
- [转] js网络请求跨域问题汇总(携带cookie)
- ASP.NET Core 3.0 WebApi 系列【2】.Net Core 3.0+ CodeFirst + MySql 实现数据的迁移
- jQuery.form 上传文件
- Python——数据分析,Numpy,Pandas,matplotlib
- 解决ubuntu安装ssh服务无法打开解析包问题
- Markdown随笔
- SQL 分组后只获取每组的一条数据
- Java JMS——消息服务
- [转]【Servlet】Servlet的访问过程