1、求最大公约数（gcd）
最大公约数（greatest common divisor，简写为 gcd ；或highest common factor，简写为hcf)，指某几个整数共有因子中最大的一个。
（1）更相减损术
更相减损术百度百科
代码如下：
非递归形式
int gcd(int a, int b) {
while (a != b)
{
if (a > b)
a -= b;
else
b -= a;
}
return a;
}
递归形式
这个gcd函数在正int型内完全通用，返回a,b的最大公约数
但是当a,b之间差距较大时（如100000倍）会导致错误（栈过深）
int gcd(int a, int b) {
if (a == b)return a;
else if (a > b)a -= b;
else b -= a;
return gcd(a, b);
}
（2）辗转相除法（欧几里得算法）
欧几里得算法百度百科
代码如下：
非递归形式：
int gcd(int a, int b) {
int temp = b;
while (a % b) {
temp = a % b;
a = b;
b = temp;
}
return temp;
}
递归形式：
int gcd(int a, int b)
{
if (a % b == 0) return b;
else return gcd(b, a % b);
}
（3）求多个数的最大公约数
我们可以先求出前两个数的最大公约数(a)，再用这个最大公约数(a)与下一个数求出它们的最大公约数(b)，不断循环直到计算完所有数。
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
if (a % b == 0) return b;
else return gcd(b, a % b);
}
int main()
{
int a[8] = { 32,16,12,24,36,20,40,28 };
int L = sizeof(a) / sizeof(int);
int m = a[0];
for (int i = 1; i < L; i++) {
m = gcd(m, a[i]);
}
cout << m;
return 0;
}
上面这种算法很直观，但是会不断调用内部有多次循环的 gcd 算法，在计算大数时较为复杂。因此推荐下面这种优化算法：
（1）对这一组数从大到小进行排序
（2）对每两个相邻的两个数进行如下操作：
设相邻的两个数为A和B（A在前，因为已经排序，所以A>B），如果A=n*B（n为整数）,也就是A能够被B整除，那么就令A=B；如果A不能被B整除则令A=A%B。
（3）重复（1）、（2）直到数组中每个数都相等，则最大公约数就为这个数。
#include <algorithm>
#include <iostream>
using namespace std;
bool cmp(int a, int b) {
return a > b;
}
int gcd(int num[], int n)
{
sort(num, num + n, cmp);
while (num[0] != num[n - 1]) {
for (int i = 0; i < n - 1; i++) {
if (num[i] % num[i + 1] == 0)
num[i] = num[i + 1];
else
num[i] = num[i] % num[i + 1];
}
sort(num, num + n, cmp);
}
return num[0];
}
int main()
{
int a[8] = { 32,16,12,24,36,20,40,28 };
int L = sizeof(a) / sizeof(int);
cout << gcd(a, L);
return 0;
}
2、求最小公倍数（lcm）
两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数（Least Common Multiple，简写为 lcm）。
（1）求两个数的最小公倍数
对于两个数，它们的最小公倍数等于两数之积除以最大公约数
公式：最小公倍数=两数乘积/最大公约数
int gcd(int a, int b)
{
if (a % b == 0) return b;
else return gcd(b, a % b);
}
int lcm(int a, int b) {
int temp = a * b;
temp = temp / gcd(a, b);
return temp;
}
（2）求多个数的最小公倍数
我们可以先求出前两个数的最小公倍数(a)，再用这个最小公倍数(a)与下一个数求出它们的最小公倍数(b)，不断循环直到计算完所有数。
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
if (a % b == 0) return b;
else return gcd(b, a % b);
}
int lcm(int a, int b) {
int temp = a * b;
temp = temp / gcd(a, b);
return temp;
}
int main()
{
int a[4] = { 40,20,10,30 };
int L = sizeof(a) / sizeof(int);
int m = a[0];
for (int i = 1; i < L; i++) {
m = m * a[i] / gcd(m, a[i]);
}
cout << m;
return 0;
}
最后给个求多个数的最大公约数的例题
Lowest Common Multiple Plus
求n个数的最小公倍数。
Input
输入包含多个测试实例，每个测试实例的开始是一个正整数n，然后是n个正整数。
Output
为每组测试数据输出它们的最小公倍数，每个测试实例的输出占一行。你可以假设最后的输出是一个32位的整数。
Sample Input
2 4 6
3 2 5 7
Sample Output
12
70
这题要考虑数据类型，我直接给了long long
AC代码：
#include <iostream>
using namespace std;
#define ll long long
ll a[10000];
ll gcd(ll a, ll b)
{
if (a % b == 0) return b;
else return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
ll temp = a * b;
temp = temp / gcd(a, b);
return temp;
}
int main()
{
int n;
while (cin >> n) {
for (int i = 0; i < n; i++) {
cin >> a[i];
}
ll m = a[0];
for (int i = 1; i < n; i++) {
m = m * a[i] / gcd(m, a[i]);
}
cout << m << endl;
}
return 0;
}
|