首页 » Program » C/C++ » 正文

n个数求lcm的两种方法

第一种:逐乘算法(我自己起的名字)
根据最小公倍数一定是最大那个数的整数倍

#include <stdio.h>
int main()
{
    int a[1000],i,flag,lcm,n,m,count,lc;
    scanf("%d",&n);
    while (n--)
        {
            lcm = 0;
            scanf("%d",&m);
            for (i=0; i<m; i++)
                {
                    scanf("%d",&a[i]);
                    if (lcm<a[i]) lcm = a[i];  //求最大值
                }
            flag = 1;
            count = 2;
            lc = lcm;
            while (1)
                {
                    for (i=0; i<m; i++)
                        {
                            if (lcm % a[i]!=0)  //不能整除说明不是最小公倍数
                                {
                                    flag = 0;   //标志
                                    lcm = count * lc;   //找最小公倍数
                                    count++;
                                    break;
                                }
                            else flag = 1;
                        }
                    if (flag)  //flag=1就表明是最小公倍数
                        {
                            printf("%d\n",lcm);
                            break;
                        }
                }
        }
    return 0;
}


第二种:
根据两个数的最小公倍数等于那两个数的乘积除以那两个数的最大公约数,在把前两个数求到的最小公倍数和后面的数求最小公倍数,以此类推,利用辗转相除法

#include <stdio.h>
int main()
{
    int gcd(int a,int b);
    int str[1000],n,m,i,lcm;
    scanf("%d",&n);
    while (n--)
        {
            scanf("%d",&m);
            for (i=0; i<m; i++)
                {
                    scanf("%d",&str[i]);
                }
            if (m==1) printf("%d\n",str[0]);
            else
                {
                    lcm = str[0] / gcd(str[0],str[1]) * str[1];   //先求前两个数的最小公倍数(那两个数相乘再除最大公约数)
                    for (i=2; i<m; i++)
                        {
                            lcm = str[i] / gcd(lcm,str[i]) * lcm;   //前两个数的最小公倍数作为一个数和第三个数求最小公倍数(以此类推)
                        }
                    printf("%d\n",lcm);
                }
        }
    return 0;
}

int gcd(int a,int b)   //辗转相除法
{
    int t;
    if (a<b)  //小的数放后面
        {
            t = a;
            a = b;
            b = t;
        }
    if (a % b==0)
        return b;   //b就是最大公约数了
    else
        return gcd(b,a % b);   //传小的和余数
}

以上两种方法亲测可行,杭电acm1019可以利用这两种方法都可以ac
http://acm.hdu.edu.cn/showproblem.php?pid=1019

赞 (0)

Comment