数论 GCD 最大公约数
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了数论 GCD 最大公约数,现在分享给大家,供学习和参考。文章包含1040字,纯文字阅读大概需要3分钟。
教程信息
GCD:求最大公约数
最大公约数(greatest common divisor
,简写为 gcd
;或highest common factor
,简写为hcf
),指某几个整数共有因子中最大的一个
。
输入整数a和b,求这两个数的最大公约数。
方法一:暴力枚举
实现逻辑:
通过比较小的数,循环一个个去试,思路简单
但是效率低下
。
这样写的时间复杂度是O(min(a,b)),一旦A,B都特别大的时候(比如说都是2的31次方),这种方法的运行速度将会比乌龟还慢,自然会时间超限(TLE)
。
实现代码:
#include <bits/stdc++.h> using namespace std; int gcd(int a,int b) { // 取小数倒序循环测试 for(int i=min(a,b);i>=1;i--){ // 能同时被整除的最大的数 if(a%i==0&&b%i==0) { return i; } } } int main(){ int a,b; cin>>a>>b; int result=gcd(a,b); cout<<result; return 0; }
实现结果:
方法二、辗转相除法,欧几里得算法
实现逻辑:
辗转相除法就是定义一个变量R来储存A模B的值,再将A的值设为B,B的值设为R。以此类推,直到B=0为止。然后直接输出A就行了。
时间复杂度获得了飞跃性的提升。
1.引入要求的两个数a和b 2.大的数除以小的数,然后把大的数用余数代替(重复的逻辑) 3.余数为零时,可求出最大公约数(边界)
实现代码(while写法):
#include <bits/stdc++.h> using namespace std; int gcd(int a,int b) { while(b>0) { int r=a%b; a=b;b=r; } return a; } int main(){ int a,b; cin>>a>>b; int result=gcd(a,b); cout<<result; return 0; }
实现代码(递归写法):
#include <bits/stdc++.h> using namespace std; int gcd(int a,int b) { if(b==0) { return a; } else { return gcd(b,a%b); } } int main(){ int a,b; cin>>a>>b; int result=gcd(a,b); cout<<result; return 0; }
实现结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供数论 GCD 最大公约数的全部内容,希望教程文章能够帮你了解学习数论 GCD 最大公约数,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaozhongji-244.html