精华内容
下载资源
问答
  • 多个数最小公倍数

    2014-03-30 19:10:34
    * 功能:计算并返回多个数字的最小公倍数. *   * 说明:调用函数:INT lcm(INT a, INT b); *   *****************************************************************************/   INT  LcmN( ...
    1. typedef int             INT;  
    2.   
    3. INT gcd(INT a, INT b);  
    4. INT lcm(INT a, INT b);  
    5.   
    6. /***************************************************************************** 
    7. * 函数:LcmN                                                                * 
    8. * 参数:pnNum:数字数组.                                                         * 
    9. *      nLen:数字个数.                                                        * 
    10. * 返回值:返回多个数字的最小公倍数.                                          * 
    11. * 功能:计算并返回多个数字的最小公倍数.                                        * 
    12. * 说明:调用函数:INT lcm(INT a, INT b);                                         * 
    13. *****************************************************************************/  
    14. INT LcmN(INT *pnNum, INT nLen)  
    15. {  
    16.     INT i;  
    17.     INT nRes;  
    18.   
    19.     if (nLen < 0)  
    20.         return -1;  
    21.     if (1 == nLen)  
    22.         return pnNum[0];  
    23.   
    24.     nRes = lcm(pnNum[0], pnNum[1]);  
    25.     for (i=2; i<nLen; i++)  
    26.         nRes = lcm(nRes, pnNum[i]);  
    27.   
    28.     return nRes;  
    29. }  
    30.   
    31. /***************************************************************************** 
    32. * 函数:gcd                                                                     * 
    33. * 参数:a:数字1.                                                              * 
    34. *      b:数字2.                                                                * 
    35. * 返回值:返回a和b的最大公约数.                                               * 
    36. * 功能:计算并返回a和b的最大公约数(递归版本).                               * 
    37. *****************************************************************************/  
    38. /* 
    39. INT gcd(INT a, INT b) 
    40. { 
    41.     if (0 == b) 
    42.         return a; 
    43.     return gcd(b, a % b); 
    44. } 
    45. */  
    46.   
    47. /***************************************************************************** 
    48. * 函数:gcd                                                                     * 
    49. * 参数:a:数字1.                                                              * 
    50. *      b:数字2.                                                                * 
    51. * 返回值:返回a和b的最大公约数.                                               * 
    52. * 功能:计算并返回a和b的最大公约数(循环版本).                               * 
    53. *****************************************************************************/  
    54. INT gcd(INT a, INT b)  
    55. {  
    56.     INT nTem;  
    57.   
    58.     while (0 != b)  
    59.     {  
    60.         nTem = b;  
    61.         b = a % b;  
    62.         a = nTem;  
    63.     }  
    64.   
    65.     return a;  
    66. }  
    67.   
    68. /***************************************************************************** 
    69. * 函数:lcm                                                                     * 
    70. * 参数:a:数字1.                                                              * 
    71. *      b:数字2.                                                                * 
    72. * 返回值:返回a和b的最小公倍数.                                               * 
    73. * 功能:计算并返回a和b的最小公倍数.                                             * 
    74. * 说明:调用函数:INT gcd(INT a, INT b);                                         * 
    75. *****************************************************************************/  
    76. INT lcm(INT a, INT b)  
    77. {  
    78.     return a / gcd(a, b) * b;  
    79. }  
    展开全文
  • 求两个数最大公约数 int gcd(int n,int m) ...求两个数最小公倍数 int lcm(int n,int m,int r) { return n*m/r;//n,m分别是两个数,r是两个数的最大公约数 } 求n个数的最小公倍数 #include&l...

    求两个数最大公约数

    int gcd(int n,int m)
    {
        return m>0?gcd(m,n%m):n;
    }
    

    求两个数最小公倍数

    int lcm(int n,int m,int r)
    {
        return n*m/r;//n,m分别是两个数,r是两个数的最大公约数
    }
    

    求n个数的最小公倍数

    #include<iostream>
    using namespace std;
    int gcd(int n,int m)
    {
        return m>0?gcd(m,n%m):n;
    }
    int lcm(int n,int m,int r)
    {
        return n*m/r;//n,m分别是两个数,r是两个数的最大公约数
    }
    int main()
    {
        int n,k;
        int a[50];
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>a[i];
            k=1;
            for(int i=0;i<n;i++)
            {
                k=lcm(k,a[i],gcd(k,a[i]));
            }
            cout<<k<<endl;
        return 0;
    }
    

    求多个数的最大公约数

    #include<iostream>
    #include<stdio.h>
    using namespace std;
    int gcd(int n,int m)
    {
        return m>0?gcd(m,n%m):n;
    }
    int lcm(int n,int m,int r)
    {
        return n*m/r;//n,m分别是两个数,r是两个数的最大公约数
    }
    int main()
    {
        int n,k;
        int a[50];
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>a[i];
            k=gcd(a[0],a[1]);
            for(int i=2;i<n;i++)
            {
                k=gcd(k,a[i]);
            }
            cout<<k<<endl;
        return 0;
    }
    

      

    转载于:https://www.cnblogs.com/caijiaming/p/9147018.html

    展开全文
  • 多个数最小公倍数的一种变换算法  2011-07-21 10:39:49| 分类: C++|举报|字号 订阅 令[a1,a2,..,an] 表示a1,a2,..,an的最小公倍数,(a1,a2,..,an)表示a1,a2,..,an的最大公约数,其中a1,...

    求多个数最小公倍数的一种变换算法  

    2011-07-21 10:39:49|  分类: C++|举报|字号 订阅

    令[a1,a2,..,an] 表示a1,a2,..,an的最小公倍数,(a1,a2,..,an)表示a1,a2,..,an的最大公约数,其中a1,a2,..,an为非负整数。对于两个数a,b,有[a,b]=ab/(a,b),因此两个数最小公倍数可以用其最大公约数计算。但对于多个数,并没有[a1,a2,..,an]=M/(a1,a2,..,an)成立,M为a1,a2,..,an的乘积。例如:[2,3,4]并不等于24/(2,3,4)。即两个数的最大公约数和最小公倍数之间的关系不能简单扩展为n个数的情况。

    本文对多个数最小公倍数和多个数最大公约数之间的关系进行了探讨。将两个数最大公约数和最小公倍数之间的关系扩展到n个数的情况。在此基础上,利用求n个数最大公约数的向量变换算法计算多个数的最小公倍数。

     

    1.  多个数最小公倍数和多个数最大公约数之间的关系

    令p为a1,a2,..,an中一个或多个数的素因子,a1,a2,..,an关于p的次数分别为r1,r2,..,rn,在r1,r2,..,rn中最大值为rc1=rc2=..=rcm=rmax,最小值为rd1=rd2=..=rdt=rmin,即r1,r2,..,rn中有m个数所含p的次数为最大值,有t个数所含p的次数为最小值。例如:4,12,16中关于素因子2的次数分别为2,2,4,有1个数所含2的次数为最大值,有2个数所含2的次数为最小值;关于素因子3的次数分别为0,1,0,有1个数所含3的次数为最大值,有2个数所含3的次数为最小值。

    对最大公约数有,只包含a1,a2,..,an中含有的素因子,且每个素因子次数为a1,a2,..,an中该素因子的最低次数,最低次数为0表示不包含[1]。

    对最小公倍数有,只包含a1,a2,..,an中含有的素因子,且每个素因子次数为a1,a2,..,an中该素因子的最高次数[1]。

     

    定理1:[a1,a2,..,an]=M/(M/a1,M/a2,..,M/an),其中M为a1,a2,..,an的乘积,a1,a2,..,an为正整数。

    例如:对于4,6,8,10,有[4,6,8,10]=120,而M=4*6*8*10=1920,M/(M/a1,M/a2,..,M/an) =1920/(6*8*10,4*8*10,4*6*10,4*6*8)=1920/16=120。

    证明:

    M/a1,M/a2,..,M/an中p的次数都大于等于r1+r2+..+rn-rmax,且有p的次数等于r1+r2+..+rn-rmax的。这是因为

    (1)       M/ai中p的次数为r1+r2+..+rn-ri,因而M/a1,M/a2,..,M/an中p的次数最小为r1+r2+..+rn-rmax。

    (2)       对于a1,a2,..,an中p的次数最大的项aj(1项或多项),M/aj中p的次数为r1+r2+..+rn-rmax。

    或者对于a1,a2,..,an中p的次数最大的项aj,M/aj中p的次数小于等于M/ak,其中ak为a1,a2,..,an中除aj外其他的n-1个项之一,而M/aj中p的次数为r1+r2+..+rn-rmax。

    因此,(M/a1,M/a2,..,M/an)中p的次数为r1+r2+..+rn-rmax,从而M/(M/a1,M/a2,..,M/an)中p的次数为rmax。

    上述的p并没有做任何限制。由于a1,a2,..,an中包含的所有素因子在M/(M/a1,M/a2,..,M/an)中都为a1,a2,..,an中的最高次数,故有[a1,a2,..,an]=M/(M/a1,M/a2,..,M/an)成立。

    得证。

     

    定理1对于2个数的情况为[a,b]=ab/(ab/a,ab/b)=ab/(b,a)=ab/(a,b),即[a,b]=ab/(a,b)。因此,定理1为2个数最小公倍数公式[a,b]=ab/(a,b)的扩展。利用定理1能够把求多个数的最小公倍数转化为求多个数的最大公约数。

     

    2.多个数最大公约数的算法实现

    根据定理1,求多个数最小公倍数可以转化为求多个数的最大公约数。求多个数的最大公约数(a1,a2,..,an)的传统方法是多次求两个数的最大公约数,即

    (1)       用辗转相除法[2]计算a1和a2的最大公约数(a1,a2)

    (2)       用辗转相除法计算(a1,a2)和a3的最大公约数,求得(a1,a2,a3)

    (3)       用辗转相除法计算(a1,a2,a3)和a4的最大公约数,求得(a1,a2,a3,a4)

    (4)       依此重复,直到求得(a1,a2,..,an)

    上述方法需要n-1次辗转相除运算。

    本文将两个数的辗转相除法扩展为n个数的辗转相除法,即用一次n个数的辗转相除法计算n个数的最大公约数,基本方法是采用反复用最小数模其它数的方法进行计算,依据是下面的定理2。

    定理2:多个非负整数a1,a2,..,an,若aj>ai,i不等于j,则在a1,a2,..,an中用aj-ai替换aj,其最大公约数不变,即 (a1,a2,..,aj-1,aj,aj+1,..an)=(a1,a2,..,aj-1,aj-ai,aj+1,..an)。

    例如:(34,24,56,68)=(34,24,56-34,68)=(34,24,22,68)。

    证明:

    根据最大公约数的交换律和结合率,有

    (a1,a2,..,aj-1,aj,aj+1,..an)= ((ai,aj),(a1,a2,..,ai-1,ai+1,..aj-1,aj+1,..an))(i>j情况),或者

    (a1,a2,..,aj-1,aj,aj+1,..an)= ((ai,aj),(a1,a2,..,aj-1,aj+1,..ai-1,ai+1,..an))(i<j情况)。

    而对(a1,a2,..,aj-1,aj-ai,aj+1,..an),有

    (a1,a2,..,aj-1,aj-ai,aj+1,..an)= ((ai, aj-ai),( a1,a2,..,ai-1,ai+1,.. aj-1,aj+1,..an))(i>j情况),或者

    (a1,a2,..,aj-1,aj-ai,aj+1,..an)= ((ai, aj-ai),( a1,a2,..,aj-1,aj+1,.. ai-1,ai+1,..an))(i<j情况)。

    因此只需证明(ai,aj)=( ai, aj-ai)即可。

    由于(aj-ai)= aj-ai,因此ai,aj的任意公因子必然也是(aj-ai)的因子,即也是ai,( aj-ai)的公因子。由于aj = (aj-ai)+ai,因此ai,( aj-ai)的任意公因子必然也是aj的因子,即也是ai,aj的公因子。所以,ai,aj的最大公约数和ai,(aj-ai) 的最大公约数必须相等,即(ai,aj)=(ai,aj-ai)成立。

    得证。

     

    定理2类似于矩阵的初等变换,即

    令一个向量的最大公约数为该向量各个分量的最大公约数。对于向量<a1,a2,..,an>进行变换:在一个分量中减去另一个分量,新向量和原向量的最大公约数相等。

     

    求多个数的最大公约数采用反复用最小数模其它数的方法,即对其他数用最小数多次去减,直到剩下比最小数更小的余数。令n个正整数为a1,a2,..,an,求多个数最大共约数的算法描述为:

    (1)       找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个

    (2)       aj以外的所有其他非0项ak用ak mod aj代替;若没有除aj以外的其他非0项,则转到(4)

    (3)       转到(3)

    (4)       a1,a2,..,an的最大公约数为aj

    例如:对于5个数34, 56, 78, 24, 85,有

    (34, 56, 78, 24, 85)=(10,8,6,24,13)=(4,2,6,0,1)=(0,0,0,0,1)=1,

    对于6个数12, 24, 30, 32, 36, 42,有

    (12, 24, 30, 32, 36, 42)=(12,0,6,8,0,6)=(0,0,0,2,0,6)=(0,0,0,2,0,0)=2。

    3. 多个数最小共倍数的算法实现

           求多个数最小共倍数的算法为:

    (1)       计算m=a1*a2*..*an

    (2)       把a1,a2,..,an中的所有项ai用m/ai代换

    (3)       找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个

    (4)       aj以外的所有其他非0项ak用ak mod aj代替;若没有除aj以外的其他非0项,则转到(6)

    (5)       转到(3)

    (6)       最小公倍数为m/aj

    上述算法在VC环境下用高级语言进行了编程实现,通过多组求5个随机数最小公倍数的实例,与标准方法进行了比较,验证了其正确性。标准计算方法为:求5个随机数最小公倍数通过求4次两个数的最小公倍数获得,而两个数的最小公倍数通过求两个数的最大公约数获得。

    5.结论

    计算多个数的最小公倍数是常见的基本运算。n个数的最小公倍数可以表示成另外n个数的最大公约数,因而可以通过求多个数的最大公约数计算。求多个数最大公约数可采用向量转换算法一次性求得。

    展开全文
  • 最小公倍数算法 View Code ... 2 /*两个数最小公倍数*/ 3 #include<stdio.h> 4 int main() 5 { 6 int t,x,y,r,p,b; 7 scanf("%d",&t); 8 while(t--) 9 { 10 scanf("%d%d...

    最小公倍数算法

    View Code
     1 View Code 
     2  /*两个数的最小公倍数*/
     3  #include<stdio.h>
     4  int main()
     5  {
     6   int t,x,y,r,p,b;
     7   scanf("%d",&t);
     8   while(t--)
     9   {
    10    scanf("%d%d",&x,&y);
    11    if(x==0||y==0)
    12    {
    13        b=0;break;
    14    }
    15    if(x<y)
    16    {
    17     p=x;x=y;y=p;
    18    }
    19 
    20    b=x;
    21    while(b%y!=0)
    22    {
    23     b=b+x;
    24    }
    25    printf("%d\n",b);
    26   }
    27   return 0;
    28  }
    29  /*
    30  1
    31  2 5
    32  10
    33  */
    34  
    35  /*多个数的最小公倍数*/
    36  #include<stdio.h>
    37  int power(int x,int y)
    38  {
    39   int b,t;
    40   if(x<y)
    41   {
    42    t=x;x=y;y=t;
    43   }
    44   b=x;
    45   while(b%y!=0)
    46   {
    47    b=b+x;
    48   }
    49   return b;
    50  }
    51  int main()
    52  {
    53   int s,n,i,t;
    54   while(scanf("%d",&n)!=-1)
    55   {
    56    t=1;
    57    for(i=1;i<=n;i++)
    58    {
    59     scanf("%d",&s);
    60     if(s==0)//当数字中有零时,要格外考虑
    61     {
    62         t=0;break;
    63     }
    64     t=power(s,t);
    65    }
    66    printf("%d\n",t);
    67   }
    68   return 0;
    69  }
    70  /*
    71  3
    72  2 5 7
    73  70
    74  */

     

    转载于:https://www.cnblogs.com/zlyblog/archive/2012/07/07/2580706.html

    展开全文
  • 令[a1,a2,..,an] 表示a1,a2,..,an的...对于两个数a,b,有[a,b]=ab/(a,b),因此两个数最小公倍数可以用其最大公约数计算。但对于多个数,并没有[a1,a2,..,an]=M/(a1,a2,..,an)成立,M为a1,a2,..,an的乘积。例如:[2,3
  • 答案是a, b, c的最小公倍数。 问题描述 小张是软件项目经理,他带领3开发组。工期紧,今天都在加班呢。为鼓舞士气,小张打算给每组发一袋核桃(据传言能补脑)。他的要求是: 1. 各组的核桃数量...
  • 思路:暴力枚举每4个数最小公倍数。答案即为这些最小公倍数*k中。求法参考 http://blog.163.com/ocean_123/blog/static/1908970672011621103949535/ 代码: #include #include const int MAXN = 55; ...
  • 辗转相除法求其最小公倍数,实用性强   #include #include #include using namespace std; int rem(int a,int b) { int c=a%b; //printf("a %d a\n",a); //printf("b %d b\n",b); //printf("c %d c\n",c)...
  • 一种是最容易想到的穷举法:最小公倍数肯定大于等于两个数的最大数,因此从最大数开始,用循环语句使不断增加,当增加到某个数可与i同时整除这两个数时,该数则为这两个数最小公倍数。 一种是使用公式a * b=gcd* ...
  • 多个数最小公倍数公倍数,这个名词对于我们来说也并不陌生,通常玩的也就是两个数的最小公倍数,今天我们就来玩一玩多个数最小公倍数。 公倍数,这个名词对于我们来说也并不陌生,通常玩的也就是两个数的最小...
  • 多个数最小公倍数

    2016-12-11 20:29:06
    思路:求多个数最小公倍数的思想:先求出两个数的最小公倍数,然后将他们的最小公倍数与第三个数求最小公倍数,由此递推求多个数最小公倍数。#include #include using namespace std; int gcd(int x,int y) //求两...
  • 多个数最小公倍数

    2018-01-11 19:00:18
    多个数最小公倍数 问题描述: 输入多个数求这个数的最小公倍数。 输入: 输入包含多组测试数据,每组数据的第一行为输入数据的个数n(n 输出: 输出为n个数的最小公倍数。 输入样例: 3 2 6 9 0 输出样例...
  • 今天参加腾讯笔试,做编程题时在最小公倍数、最大公约数这些这么简单的知识点上卡壳了,...3、求两个数最小公倍数,两个数最小公倍数与它们的最大公约数之间存在如下关系: 某两个数a,b的最小公倍数=(a*b)/a与b...
  • 多个数最小公倍数的一种变换算法  令[a1,a2,..,an] 表示a1,a2,..,an的最小公倍数,(a1,a2,..,an)表示a1,a2,..,an的最大公约数,其中a1,a2,..,an为非负整数。对于两个数a,b,有[a,b]=ab/(a,b),因此两个数最小公...
  • 多个数放在一个数组arr中 求出数组前两个数(arr[0]和arr[1])的最小公倍数 min 求出前两个数出的最小公倍数与第三个数(min和arr[2])的最小公倍数,此时得到的最小公倍数就是数组前3个数的最小公倍数,以此类推。 ...
  • 有了公式,我们很清楚可以知道了,只要有最大公约数就可以求出最小公倍数,因为两数乘积肯定是已知的,所以下面将讲解一下两个数如何求最大公约数。 1.辗转相除法(方法有很,只介绍我会的,并且易懂的h...
  • 那么如何求多个数最小公倍数呢,道理也是一样,两两求最小公倍数,然后再拿这个结果去和别的数求最小公倍数就行了,详解见https://www.luogu.com.cn/blog/zzj/ti-xie-p4057-chen-pao-post 其实这是水题,毕竟普及难度,...
  • 数学算法:求多个数最小公倍数

    万次阅读 2017-03-25 10:16:30
    2、运用小学奥数的算法,多个数最小公倍数,先将两个数的最小公倍数求出,再与后面的数求最小公倍数。两个数的最小公倍数,可以先将两个数相乘再除两个数的最小公因数。为了避免溢出,可以先相除再相乘。题目:...
  • 题意: 求多个数最小公倍数 题解: 没什么好说的,数不会太多,挨个求相邻两个数的最小公倍数,得到的这个数与下一个数继续求最小公倍数,直到最后一个数结束。最小公倍数 = x * y / x、y的最小公约数。 过程中犯...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,140
精华内容 456
关键字:

多个数最小公倍数