题解 | #小乐乐与欧几里得#

小乐乐与欧几里得

https://www.nowcoder.com/practice/da13e0cf321e4df9acd0fdf0a433cbb0

#include <stdio.h>
long long test1(long long a, long long b)    //使用迭代方法实现欧几里得算法求最大公约数
{
    if (a == 0 || b == 0)
    {
        return 0;
    }
    long long r = a % b;
    while (r != 0)
    {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}
long long test2(long long a, long long b)    //使用递归方法实现欧几里得算法求最大公约数
{
    if (a == 0 || b == 0)
    {
        return 0;
    }
    else if (a % b == 0)
        return b;
    else
    {
        long long r = a % b;
        return test2(b, r);
    }
}
int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    long long result1 = test2(a, b);
    long long result2 = a / result1 * b / result1 * result1;        //不要为了这部分性能而影响代码可读性
    printf("%ld", result1 + result2);
}

1.显然不可能暴力解,10^8级数据肯定会爆炸

2.考虑到两个十亿以内的数的最小公倍数可能会很大,所以选择long long,2^63估算上限在10^18数量级,不会溢出

3.辗转相除法/欧几里得算法求最大公约数的原理:https://www.bilibili.com/video/BV1my4y1z7Zn/?spm_id_from=333.337.search-card.all.click&vd_source=441d2aa2c4bb2a4eccbf0d3f0f77398d

原理证明的基本思路:证(a,b)的公因数一定是r的公因数,证(b,r)的公因数也一定是a的公因数,所以(a,b)的公因数一定是(b,r)的公因数,(b,r)的公因数也一定是(a,b)的公因数,所以两者的公因数完全相同,所以最大公因数也相同。

4.可以采用递归或者迭代的方法来实现,此外,可以不用考虑a=0或b=0的情况,题目已说明是正整数。但是要了解,输入0会崩溃。

全部评论

相关推荐

完美的潜伏者许愿简历...:隐藏信息被你提取出来了,暗示,这就是暗示
点赞 评论 收藏
分享
06-10 23:36
已编辑
首都经济贸易大学 C++
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务