题解 | #最大公约数#

最大公约数

http://www.nowcoder.com/practice/cf4091ca75ca47958182dae85369c82c

求最大公约数
1、辗转相除法
gcd(a,b)=gcd(b,a%b)
若要求(a,b)的公约数等于(a,a%b)的公约数,当a%b==0时,b为最大公约数;

class Solution {
public:
    int gcd(int a, int b) {
        if(a%b==0){return b;}
        else{return gcd(b,a%b);}
    }
};

2、更相减损法
性质:两个数的最大公约数等于两个数中较小的和两数之差的最大公约数。

class Solution {
public:
    int gcd(int a, int b) {
        int temp = abs(a - b); //取差的绝对值 
        while(temp != 0) //不断减去差的绝对值直到为0
        {
            a = b;
            b = temp;
            temp = abs(a - b);
        }
        return b;
    }
};

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议