【一天一练】【2014.5.31】【最大公约数和最小公倍数】

李掌柜

题目描述
输入两个正整数m和n，求其最大公约数和最小公倍数。

输入
两个整数

输出
最大公约数，最小公倍数

样例输入
5 7

样例输出
1 35

注：1 本题目来源http://www.clang.cc
        2 所有做题并贴代码的小伙伴都有机会获得1~5个啊哈币

游客，如果您要查看本帖隐藏内容请回复

mengyizui

还是沙发

#include <stdio.h>

int main (void)
{
        int a = 0;
        int b = 0;
        int gy = 0;
        int gb = 0;
        int i = 0;
        scanf ("%d %d", &a, &b);
        gb = a*b;
        while (( a % 2 == 0 ) && ( b % 2 == 0 ))
        {
                a = a / 2; b = b / 2;
                ++i;
        }
        while (a!=b)
        {
                if (a > b)
                        a -= b;
                if (b > a)
                        b -= a;
        }
        gy = a*( i == 0 ? 1 : 2 * i );
        gb /= gy;
        printf ("%d %d",gy,gb);
        return 0;
}
公式根据《九章算术》更相减损法，看不懂的自行百度。数学小白，只能把别人的数学方法用编程解释出来了。。。

zhuzhu81998

会最小公倍数的正在研究怎么求最大公因数

邀请码

看着论坛里这么多挖坟的，我也想挖坟。。。
#include <iostream>
using namespace std;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
int main()
{
    int a,b;
    cin >> a >> b;
    cout << gcd(a,b) << ' ';
    cout << a*b/gcd(a,b);
    return 3-3;
}

温志浩

1111111111111111111111