侧边栏壁纸
  • 累计撰写 781 篇文章
  • 累计创建 1 个标签
  • 累计收到 1 条评论
标签搜索

辗转相除法

Dettan
2022-01-09 / 0 评论 / 0 点赞 / 25 阅读 / 550 字
温馨提示:
本文最后更新于 2022-04-30,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
用来求最大公约数
计算两个整数最大公约数 \text{gcd}(a, b)gcd(a,b) 的一种常见方法是欧几里得算法,即辗转相除法。
核心部分为:
gcd(a,b)=gcd(b,a mod b)

1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此,最大公约数为1


1995 / 615 = 3 ( 余 150 )
615 / 150 = 4 ( 余 15 )
150 / 15 = 10 ( 余 0 )
至此,最大公约数为15

function gcd(a, b) {
    if (a % b == 0) return b;
    return gcd(b, a % b);
}
int gcd(int m,int n)
{   
		if(n == 0){
        return m; 
    }
    int r = m%n;
    return gcd(n,r);
}
作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/find-greatest-common-divisor-of-array/solution/zhao-chu-shu-zu-de-zui-da-gong-yue-shu-b-brqd/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

0

评论区