河北大学程序设计训练营

[TOC]

day15 最大公约数和最小公倍数

本题要求两个给定正整数的最大公约数和最小公倍数。

输入格式:

输入在一行中给出两个正整数M和N（≤1000）。

输出格式:

在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。

输入样例:

1
511 292

输出样例:

1
73 2044

最大公约数：
解最大公约数常用的是欧几里得算法（辗转相除法）
欧几里得算法指出：设a,b均为正整数，a,b的最大公约数，就等于b,a%b的最大公约数，即 Gcd(a,b)=Gcd(b,a%b)。（可以通过数学方法证明结论。）

最小公倍数：
在求解最大公约数的基础上（假设g是最大公约数），我们可以得到a,b的最小公倍数是 ab/g 。很容易可以发现，a和b的最大公约数是正整数集合a,b的交集部分，而最小公倍数是为正整数集合a,b的并集。要得到并集，由于 ab 会使公因子的部分多计算一次，所以需要除掉一次公因子，就得到了ab/g 的写法。但由于 ab 在计算时可能会溢出，所以写成 a/gb ，g是a,b的最大公约数，因此 a/g 一定可以整除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;

int Gcd(int a, int b)
{
    if (b == 0) return a;
    return Gcd(b,a%b);
}

int main()
{
    int x,y;
    cin>>x>>y;
    int g=Gcd(x,y);
    int l=x/g*y;
    cout<<g<<" "<<l;
}

或者更简洁一点写成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

int Gcd(int a, int b)
{
    return !b?a:Gcd(b,a%b);
}

int main()
{
    int x,y;
    cin>>x>>y;
    int g=Gcd(x,y);
    int l=x/g*y;
    cout<<g<<" "<<l;
}