精华内容
下载资源
问答
  • 2020-12-24 17:56:40

    1 .用辗转相除法求最大公约数
    算法描述:
    m对n求余传给自己,再次求余, 若余数等于0
    则 n 为最大公约数
    2.最小公倍数 = 两个数的积 / 最大公约数

    基本思想是采用将两个数相乘,然后除以它们的最大公约数
    function getMinCommonMultiple(a, b){
      return a * b / getMaxCommonDivisor(a, b);
    }

     

    在我国古代的《九章算术》中就有记载,现摘录如下:

    约分术曰:“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”

    其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法,实际上就是辗转相除法。

    辗转相除法求最大公约数,是一种比较好的方法,比较快。

    更多相关内容
  • 多个数求最小公倍数详解!

    千次阅读 多人点赞 2019-12-30 11:40:48
    有了公式,我们很清楚可以知道了,只要有最大公约数就可以最小公倍数,因为两乘积肯定是已知的,所以下面将讲解一下两个数如何最大公约数。 1.辗转相除法(方法有很,只介绍我会的,并且易懂的h...

                                   最小公倍数


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

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

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

    1.辗转相除法(方法有很多,只介绍我会的,并且易懂的hhhh)

     

    辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。它的具体做法是:

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

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

                   15                              55
                               15=15%55
                               10=55%15
                                5=15%10
                                0=10%5(最大公约数 5 )

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

    主要就是遵循一个准则:

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

    再举一个例子求一下(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!

                                                  总结

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

     

     

     

    展开全文
  • 一种是最容易想到的穷举法:最小公倍数肯定大于等于两个数的最大,因此从最大开始,用循环语句使不断增加,当增加到某个可与i同时整除这两个数时,该则为这两个数最小公倍数。 一种是使用公式a * b=gcd* ...

    最小公倍数的两种求法:

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

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

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

    注:

    • gcdlcm代表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;
    可得公式lcm
    gcd=a
    b ;

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

    #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;
    }
    
    展开全文
  • 数学算法:求多个数最小公倍数

    万次阅读 2017-03-25 10:16:30
    2、运用小学奥数的算法,多个数最小公倍数,先将两个最小公倍数求出,再与后面的数求最小公倍数。两个最小公倍数,可以先将两个相乘再除两个的最小公因数。为了避免溢出,可以先相除再相乘。题目:...

    解体心得:
    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));
    //不是标准库中的函数
        }
    }
    
    展开全文
  • 题目链接点击打开链接题目大意为:n正整数的最小公倍数解题思路:求最小公倍数方法我们在数学中学到过,我知道的有2种方法分别是(1)最大公约数法(2)使用辗转相除法 比如:下图为 2 4 6的最小公倍数,用2...
  • 2043: 最小公倍数时间限制: 1 Sec 内存限制: 64 MB提交: 11 解决: 9您该题的状态:已完成[提交][状态][讨论版]题目描述为什么1小时有60分钟,而不是100分钟呢?这是历史上的习惯导致。但也并非纯粹的偶然:60...
  • 多个数最小公倍数

    2022-03-21 20:17:12
    题目描述 输入n个数,请计算它们的最小公倍数。如5、7、15的最小公倍数是105。 输入 首先输入一正整数T,表示测试数据的组,然后是T组的测试数据。 每组测试先输入一整数n(2
  • 最小公倍数:如果有一自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两整数来说,指该两共有倍数中最小的一。 代码如下:/// <summary>/// 最大公约数/// </summary>/// ”a”></param>/// ”b...
  • Python 求多个数最小公倍数

    千次阅读 2019-07-24 10:21:29
    Python 求多个数最小公倍数 def mcm(*num): minimum = 1 for i in num: minimum = int(i) * int(minimum) / m.gcd(int(i), int(minimum)) return int(minimum)
  • n个数最小公倍数。 输入格式 第一行一整数 n(2≤n≤20)。 第二行n整数。 输出格式 一整数,表示最小公倍数,数据保证答案不超过int范围。 输出时每行末尾的多余空格,不影响答案正确性 要求使用「...
  • show 程序代码 废话不说,直接上程序片段 nummax,nummin=eval(input("请输入两正整数,并用逗号连接:")) if (nummax % 1 !...print(str(nummax)+"和"+str(nummin)+"的最小公倍数数是:
  • 出前两个数出的最小公倍数与第三个数(min和arr[2])的最小公倍数,此时得到的最小公倍数就是数组前3个数最小公倍数,以此类推。 代码如下: smallestCommons(arr) { var minCom = arr[0] // 当前最小公倍数 ...
  • 整数的最小公倍数的三种方法,写的不好,还请指出。
  • pid=2 参考:... main那里一直过不了,不知道为啥,然后就去搜了这。即先个数最小公倍数,再将这个数和后一个数求。 参考中最大公约数用了递归的...
  • 1171 多个数最小公倍数

    千次阅读 2022-02-07 12:28:29
    也许你已经会了2个数字最小公倍数方法,但是如果求多个数字的最小公倍数,你又能找到办法吗? 输入要求 首先输入一个整数n表示有n个,然后输入这n个整数。(n<=100) 输出要求 出n个整数的最小公...
  • def Common_multiple(number1, number2): # 两个最小公倍数 while number1 % number2 !...def Maximum_common_divisor(*number): # 任意多个数最小公倍数 while len(number) > 1: numbe...
  • 设a1,a2,…,an是n个整数(n≥2,n∈N+),它们的公倍数有无穷多个,其中最小的正的公倍数m,称为a1,a2,…,an的最小公倍数最小公倍数通常用方括号表示,记为m=[a1,a2,…,an].最小公倍数有以下性质:①a1,a2...
  • n个数最小公倍数(C语言)

    千次阅读 2021-02-05 10:20:13
    n个最小公倍数。 Input 输入包含多个测试实例,每个测试实例的开始是一个正整数n,然后是n个正整数。 Output 为每组测试数据输出它们的最小公倍数,每个测试实例的输出占一行。你可以假设最后的输出是一个32位...
  • 求多个数的最大公约数,最小公倍数以及hanks博士son问题,数论问题
  • 编程n个数最小公倍数

    千次阅读 2020-04-27 14:54:35
    文章目录1 最大公约数、最小公倍数2 编程的最大公约数、最小公倍数2.1 欧几里德算法(辗转相除法)2.2 代码实现3 编程n连续数字的最小公倍数 1 最大公约数、最小公倍数 最小公倍数(Least Common ...
  • 方法来自多个数最小公倍数的一种变换算法(详见附录说明) 最小公倍数的算法由最大公约数转化而来。最大公约数可通过如下步骤求得: (1) 找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个 (2) ...
  • 递归算法个数最小公倍数 (明明可以不用递归 你偏要递归)#includeint divide(int num1, int num2);int main(){int x=15,y=7;int c=0;c=x*y/divide(x,y);printf("%d\n",c);return 0;}int divide(int num1, int ...
  • C语言n个数最小公倍数

    千次阅读 2020-03-18 12:59:19
    这是在刷杭州电子科技大学OJ... 从1开始逐一对每个数进行除余操作,仅当每余数都为0时才能作为公倍数,因为是从1开始即从小到大开始,所以第一输出的公倍数就是最小公倍数,输出后跳出循环 用例:2 4 6, 表示...
  • 这篇文章主要介绍了PHP编程最大公约数与最小公倍数方法,涉及php数学计算的相关运算技巧,需要的朋友可以参考下具体如下://最大公约数function max_pisor($a,$b){$n = min($a, $b);for($i=$n; $i>1; $i--){...
  • 2.最小公倍数/最大公约数 Type one: 2个数 """ 最大公约数 Author:Anderson Time:2020-11-4 """ def gcd(a,b): if a<b: a,b=b,a if a%b==0: return b else: return gcd(b,a%b) 思路分析:个数的最大...
  • n个数最小公倍数

    万次阅读 多人点赞 2017-10-29 18:23:58
    n个数最小公倍数 【输入描述】 第一行一个数n(n 下面n个数,integer范围内 【输出描述】 这n个数最小公倍数 【样例输入】 5 6 3 5 4 2 【样例输出】 60 【数据范围及提示】 出最大...
  • N个数的最大公约数和最小公倍数以及Hankson"逆问题"(python) 一、题目要求 1.基本要求: N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题 2.提高要求: 已知正整数a0,a1,b0,b1,...
  • 求多个数最小公倍数
  • 也许你已经会了2个数字最小公倍数方法,但是如果求多个数字的最小公倍数,你又能找到办法吗? 输入要求 首先输入一个整数n表示有n个,然后输入这n个整数。(n<=100) 输出要求 出n个整数的最小公...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,186
精华内容 6,874
关键字:

多个数求最小公倍数方法