最小公倍数

   既然想算最小公倍数，首先要清楚最小公倍数的求法，还有最大公约数的求法

   最小公倍数*最大公约数=两数乘积

 有了公式，我们很清楚可以知道了，只要有最大公约数就可以求出最小公倍数，因为两数乘积肯定是已知的，所以下面将讲解一下两个数如何求最大公约数。

1.辗转相除法（方法有很多，只介绍我会的，并且易懂的hhhh）

 

辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：

用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

好吧，定义总是那么的复杂且难懂，下面直接一张表格，实现一遍辗转相除法，聪明的你肯定一遍就看会！

如果你看懂了两个数如何求最小公倍数，那么求多个数的最小公倍数就不难了。

主要就是遵循一个准则：

先求前两个数的最小公倍，再用这个最小公倍数与下一个数求最小公倍数

再举一个例子求一下（5 7 15） 的最小公倍数
 

字迹可能有些潦草，但是很认真哈哈哈哈哈哈！

如果大致过程会了，代码肯定是会了

代码实现：

import java.math.BigInteger;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            int k = sc.nextInt();
            int sum = 1;
            for (int i = 0; i < k; i++) {
                int p = sc.nextInt();
                sum *=  p / ff(sum, p);
            }
            System.out.println(sum);
        }
    }
    public static int ff(int x,int y){
        int r ;
        while(y!=0){
            r=x%y;
            x=y;
            y=r;
        }
        return x;

    }
    }

没有考虑大数的问题，根据题意选择long还是int。

下面介绍一个杭电oj的题目，因为你即使看的再懂不去实践也是不行的！

比如杭电的2028！

                                              总结

大家共同学习，写错的地方请提出谢谢。

最小公倍数的两种求法：

一种是最容易想到的穷举法：

• 先考虑特殊情况，当较大数是较小数的整数倍时，
• 两个数互质时，可直接快速得出最小公倍数。
• 一般情况：最小公倍数肯定大于等于两个数的最大数且肯定为较大数的整数倍，因此从最大数开始，用循环语句使不断增加最大数的整数倍，当增加到某个整数倍时可与同时整除这个较小数时，该较大数的整数倍数则为这两个数的最小公倍数。

一种是使用公式a * b=gcd* lcm ,两数之积等于这两个数的最小公倍数和最大公约数的

注：

• gcd和lcm代表a和b最大公约数和最小公倍数;
• 该公式仅用于计算两个数的gcd和lcm，对多个数不成立；
• 上述穷举法中的特殊情况也可由此公式验证

公式证明：假设两个数a和b，它们的最大公约数是:gcd
那么设：a=k1gcd ; b=k2gcd ;
因为gcd为a和b的最大公约数 ，故k1和k2互质,所以k1和k2的最小公倍数为k1k2;（上述穷举法中有提到）
那a和b的最小公倍数lcm=k1k2gcd=（a/gcd）(b/gcd)gcd;
可得公式lcmgcd=ab ;

代码实现：
想了解求最大公倍数的算法可戳：最大公约数的三种算法

#include<stdio.h>
void Least_common_multiple1(int a, int b);//穷举法
void Least_common_multiple2(int a,int b);//最大公倍数法
int Greatest_common_divisor(int a, int b);
void swap(int *x, int *y);
int main()
{
	int a, b;
	printf("请输入a,b的值：");
	scanf("%d%d", &a, &b);
	if (a == 0 || b == 0)
	{
		printf("0没有最小公倍数！，请重新输入：");
		scanf("%d%d", &a, &b);
	}
	Least_common_multiple1(a, b);
	Least_common_multiple2(a, b);
	system("pause");
	return 0;
}
void Least_common_multiple1(int a, int b)//穷举法
{
	if (a<b)
	{
		swap(&a,&b);
		if (0 == a%b)
		{
			printf("%d\n", a);//当较大数可以整除较小数时，较大数即为这两个数的最小公倍数
		}
	}
	if (1 == Greatest_common_divisor(a, b))//考虑到两个数互为质数时，最小公倍数为两个数的积（可由公式a*b=gcd*lcm；gcd=1得）
	{
		printf("%d\n", a*b);
	}
	int t = a > b ? a : b;
	for (int i = t;; i+=t)
	{
		if ((i%a == 0) && (i%b == 0))
		{
			printf("%d\n", i);
			break;
		}
	}
}
void Least_common_multiple2(int a,int b)
{
	printf("%d\n", a*b / Greatest_common_divisor(a, b));
}
int Greatest_common_divisor(int a, int b)
{
	a = abs(a);
	b = abs(b);
	if (a < b)
	{
		swap(&a, &b);
	}
	while (b)
	{
		int t = a%b;
		a = b;
		b = t;
	}
	return a;
}
void swap(int *x, int *y)
{
	int t = *x;
	*x = *y;
	*y = t;
}

求多个数的最小公倍数

递归：

分析：先求得出前面数的最小公倍数，再不断将这个数与后面做最小公倍数运算，直至求完每一个数。
代码实现：

#include<stdio.h>
#define max 4
void set_array();//设置数组
void print_array();//打印数组
void swap(int *x, int *y);//交换两数的值
int Least_common_multiple(int a,int b);//求两个数的最小公倍数
int Greatest_common_divisor(int a, int b);//求两个数的最大公倍数

int main()
{
	int array[max];
	set_array(array);
	print_array(array);
	int lcm=array[0];
	for (int i = 1; i < max; i++)
	{
		lcm=Least_common_multiple(lcm, array[i]);
	}
	printf("\n%d\n", lcm);
	return 0;
}
void set_array(int *p)
{
	for (int i = 0; i < max; i++)
	{
		scanf("%d",&p[i]);
	}
}
void print_array(int *p)
{
	for (int i = 0; i < max; i++)
	{
		printf("%d\t",p[i]);
	}
}
int Greatest_common_divisor(int a, int b)
{
	if (a < b)
	{
		swap(&a, &b);
	}
	while (b)
	{
		int t = a%b;
		a = b;
		b = t;
	}
	return a;
}
void swap(int *x, int *y)
{
	int t = *x;
	*x = *y;
	*y = t;
}
int Least_common_multiple(int a, int b)
{
	return a*b / Greatest_common_divisor(a, b);
}

穷举法：

分析：一组数的最小公约数肯定在这组数的最大值和这组数的乘积之间；故从最大值开始穷举，当某个数可以整除这组所有数时，即得到这组数的最小公倍数。
代码实现：

#include<stdio.h>
#include<stdbool.h>
#define max 4
void Set_array(int *p);//设置数组
void Print_array(int *p);//打印数组
bool Determine_divisible(int *p, int lcm);//判断lcm是否可以整除p中所有数
int Max_num(int *p);//返回这组数中的最大值

int main()
{
	int array[max];
	Set_array(array);
	Print_array(array);
	int lcm = Max_num(array);
	for (int i = lcm;; i++)
	{
		if (Determine_divisible(array,i ))
		{
			printf("这组数的最小公倍数为：%d\n", i);
			break;
		}
	}
	for (int i = array[0];; i++)
	{
		if (Determine_divisible(array, i))
		{
			printf("这组数的最小公倍数为：%d\n", i);
			break;
		}
	}
	return 0;
}
void Set_array(int *p)
{
	for (int i = 0; i < max; i++)
	{
		scanf_s("%d", &p[i]);
	}
}
void Print_array(int *p)
{
	for (int i = 0; i < max; i++)
	{
		printf("%d\t", p[i]);
	}
}
bool Determine_divisible(int *p,int lcm)
{
	for (int i = 0; i < max; i++)
	{
		if (lcm%p[i]!= 0)
		{
			return false;
		}
	}
	return true;
}
int Max_num(int *p)
{
	int t=p[0];
	for (int i = 0; i < max; i++)
	{
		t = t>p[i] ? t : p[i];
	}
	return t;
}

解体心得：
1、一开始我的算法是找出最大的那个数，再将那个数一倍一倍的相加，但是会超时，因为题目的限制是32bits。（过于天真）
2、运用小学奥数的算法，多个数的最小公倍数，先将两个数的最小公倍数求出，再与后面的数求最小公倍数。两个数的最小公倍数，可以先将两个数相乘再除两个数的最小公因数。为了避免溢出，可以先相除再相乘。
3、有一个比较简单的求最大公因数的库函数调用（__gcd(int a,int b)）,但不是标准库，头文件使用万能头文件。

题目：

Problem Description
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105.



Input
Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number of integers in the set and n1 ... nm are the integers. All integers will be positive and lie within the range of a 32-bit integer.


Output
For each problem instance, output a single line containing the corresponding LCM. All results will lie in the range of a 32-bit integer.


Sample Input
2
3 5 7 15
6 4 10296 936 1287 792 1


Sample Output
105
10296


Source
East Central Northmerica 2003, Practice 

#include<bits/stdc++.h>
using namespace std;
//为了防止溢出全开long long，gcd函数是找出两个数的最大公因数（辗转相除法）；
long long gcd(long long a,long long k)
{
    if(k == 0)
        return a;
    else
        return gcd(k,a%k);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long k,cnt,a;
        a = cnt = 1;
        while(n--)
        {
            cin>>k;//一边输入一边计算，节省时间
            cnt = a/gcd(a,k)*k;//先除后乘防止溢出；
            a = cnt;
        }
        cout<<cnt<<endl;
    }
}

求最大公因数的库函数使用：

#include<bits/stdc++.h>
//好像只能使用这个头文件
using namespace std;
int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        printf("%d\n",__gcd(a,b));
//不是标准库中的函数
    }
}