扩展欧几里得算法——例题3: 最大公约数问题1
发布日期:2021-06-27 15:39:48
浏览次数:2
分类:技术文章
本文共 1068 字,大约阅读时间需要 3 分钟。
扩展欧几里得算法
扩展欧几里得算法以O(log n)的时间求出方程 的一组特解(),通解为(t为任意整数)。我个人觉得原理搞懂了很难且用处不大,知道求 特解的模板就行。
该模板用于求方程的特解, 返回值为gcd(a,b),x、y将保存一组特解。
最大公约数问题1
题目描述
输入正整数A和B,求一组X, Y,使得方程:AX+BY=GCD(A, B)
输出|X| + |Y| 最小的一组X和Y
输入
第1行:1个整数T,表示测试数据的组数 (1 <= T <= 100)
接下来T行,每行2个整数,表示A和B (1 <= A, B <= 1000)
输出
输出T行,每行2个整数,表示X和Y
样例输入
114 8
样例输出
-1 2
分析+代码
由通解公式得知,|X|+|Y| 最小的就是exgcd()求出的特解!所以直接套用扩展欧几里得算法就行。
#include#include #include #include using namespace std;int read() { int f = 1,x = 0;char s = getchar(); while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();} while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();} return x * f;}bool f[2005];int p[2005];int n,m,i,j,k,s,o,num,num1;int exgcd(int a,int b,int &x,int &y) { if(!b) { x = 1,y = 0; return a; } else { int r = exgcd(b,a % b,y,x);//很混乱,所以要好好记 y -= x * (a / b); return r; }}int main() { n = read(); while(n --) { s = read();o = read(); exgcd(s,o,i,j); printf("%d %d\n",i,j); } return 0;}
转载地址:https://blog.csdn.net/weixin_43960414/article/details/88232054 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月11日 00时12分53秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
阿里正式启动2021届春季校招!字节跳动Android面试凉凉经,实战解析
2019-04-29
阿里珍藏版Android框架体系架构手写文档,原理+实战+视频+源码
2019-04-29
零基础也能看得懂!2021中级Android开发面试解答,附赠课程+题库
2019-04-29
震惊!靠着这份面试题跟答案,复习指南
2019-04-29
Android最强保活黑科技的最强技术实现,深度解析,值得收藏
2019-04-29
Android架构师必备框架技能核心笔记,面试心得体会
2019-04-29
Android架构师必备框架技能核心笔记,高级面试题+解析
2019-04-29
android热修复框架对比,12年高级工程师的“飞升之路”,含泪整理面经
2019-04-29
Android多线程实现方式及并发与同步,技术详细介绍
2019-04-29
Android开发究竟该如何学习,成功入职字节跳动
2019-04-29
三年老Android经验面经,看看这篇文章吧!
2019-04-29
为什么Android要采用Binder作为IPC机制?成功入职腾讯
2019-04-29
海量算法高频面试题精编解析,附超全教程文档
2019-04-29
深入浅出Android性能调优,系列篇
2019-04-29
深入浅出Android性能调优,附大厂真题面经
2019-04-29
深入解析Android-AutoLayout,全网疯传
2019-04-29
深入解析android核心组件和应用框架,最全Android知识总结
2019-04-29
深入解析android核心组件和应用框架,社招面试心得
2019-04-29
深度解析跳槽从开始到结束完整流程,持续更新中
2019-04-29
深度解析跳槽从开始到结束完整流程,面试真题解析
2019-04-29