数学知识补充（裴蜀定理与扩展欧几里得算法）
【摘要】
最大公约数可以在logn的时间范围内求出来，代码很简洁，
扩展欧几里得算法的题面公式成立的充要条件就是裴蜀定理
利用欧几里得算法进行递归改变
很容易我们可以得到一组特解 1 0
余数替换法则
展开
...
最大公约数可以在logn的时间范围内求出来，代码很简洁，
扩展欧几里得算法的题面公式成立的充要条件就是裴蜀定理
利用欧几里得算法进行递归改变
很容易我们可以得到一组特解 1 0
余数替换法则
展开
然后合并同类项
由于x发生了变化，那么就要对t=x来暂存x，计算y
同理可以用yx来做 ，而yx在第11行跟换后有好处，就是递归式可以不引入中间变量t，更加简洁
文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/weixin_54227557/article/details/120801807
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）