Question

C++ 多个数求最小公倍数

题目是先输入一个N，N代表之后输入N个数求他们的最小公倍数我自己测试了几个数据是对的。 但是交到题库上就说我答案错误了是不是我有什么东西忽略了。 求解。这是错误信息；
=================/data.out
Right:14549535
-----------------
Your:654729075
=================

以下是我写的程序；
#include<iostream>

using namespace std;
int GDC(int a,int b);
int main()
{
int n,i,a[50],r,sum;
while(cin>>n)
{
sum=1;
for(i=0;i<n;i++)
{
cin>>a[i];
sum=sum*a[i];
if(i==1)
{
r=GDC(a[0],a[1]);
}
if(i>1)
{
r=GDC(a[i],r);
}
}
cout<<sum/r<<endl;
}

return 0;
}

int GDC(int a,int b)
{
if(b>a)
{
int temp=a;
a=b;
b=temp;
}
if(a % b == 0)
{
return b;
}
else
{
return GDC(b,a % b);
}
}

<!--

Answer 1

//你的代码我大概看了一下,估计问题出在所有输入数乘积那
//这个结果sum很容易会很大,超出int范围.
//下面是另一个版本,供参考
#include <iostream>
#include <vector>
using namespace std;

int gcd(int a,int b); //最大公约数
int lcm(int a,int b); //最小公倍数:两数乘积=最小公倍数与最大公约数乘积
int  main()
{
    vector <int> a;//定义向量a用来保存输入数组
    int t,k,n;
    while(cin>>n){
        for(int i=0;i!=n;++i)
        {
            cin>>k;
            a.push_back(k); //保存数据
        }
        t=lcm(a[0],a[1]);   //对向量第0,1元素求最小公倍数
        for(size_t i=2;i!=a.size();++i)
     //求最小公倍数t与向量数组其它元素的最小公倍数
        {
            t=lcm(a[i],t);      
        }
        cout<<t<<endl;//输出结果
        a.clear();//清除向量a内容,避免影响下次输入
    }
    return 0;
}   

int gcd(int a,int b) //最大公约数
{
 int r=a%b; 
 while(r){
    a=b;
    b=r;
    r=a%b;
    }
 return b;
}
int lcm(int a,int b) //最小公倍数:两数乘积=最小公倍数与最大公约数乘积
{
    return a*b/gcd(a,b);
}

测试结果:第一行单数是个数,第二行是输入数组,第三行是数组元素的最小公倍数.以此类推

Answer 2

程序的问题主要在于算法上出错，另外单词缩写也不正确（最大公约数缩写为GCD，不是GDC），虽然这个不是主要问题。计算最小公倍数的数学公式如下：

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

公式中有两点比较关键：两个数的乘积和最大公约数。很显然，需要将求多个数最小公倍数的问题，转化为求两个数的最小公倍数问题。

而程序中所写，sum代表的乘积，并不是两个数的乘积，而是多个数的乘积，所以是错误的。至于求最大公约数的算法，写得也有些复杂，写法可以简化一些。

下面给出实现的参考示例：

#include <iostream>

using namespace std;

int gcd(int a, int b);

int main() {
    int n, num[50], a, b;
    while (cin >> n) {
        if (n <= 1 || n > 50) {
            cout << "n must be [2, 50]" << endl;
            return 1;
        } else {
            cin >> num[0];
            a = num[0];
            for(int i = 1; i < n; i++) {
                cin >> num[i];
                b = num[i];
                a = (a * b) / gcd(a, b);
            }
            cout << a << endl;
        }
    }
    return 0;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

示例中，对n的输入值做了校验，由于num数组长度为50，且数字个数少于2个无意义，所以限制n的输入范围为2-50的闭区间。

求最小公倍数时，循环num数组，每次计算时，取num数组中元素作为b与a计算，结果存至a中。循环结束后，a即为它们的最小公倍数。

Answer 3

求同时n个数的最小公倍数或最大公约数,可采取单独求解的方法,即不要同时使用那种N数之积除以最大公约数的方法(不管用的,它只适合两个或少量的数才有效，因为数字越多就越容易发生内存溢出):

Answer 4

1、输入n个数，不是只定义一个50大小的数组，需要你动态分配数组
2、i=0没有处理，当i=0时 r=0 sum/r 是没有意义的
3、对于输入数字没有控制
4、求最小公倍数的算法是不对的，多个非负整数的最小公倍数不能简单的用“总的乘积/最大公约数”来求得，比如｛2，3，4｝如果按照你的方法，算出来的最大公约数是1，按照2*3*4/1求得的最小公倍数是24，事实上他们的最小公倍数是12。
求多个数最小共倍数的算法为：
（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

Answer 5

首先你的代码求得不是最小公倍数，而是最大公约数。要求a和b的最小公倍数，可以用

a*b / GCD(a, b)来求。其次，你那个最多也就能求50个数的。

#include <iostream>
using namespace std;
int GCD(int num1,int num2)
{
    if(num2 > num1)
    {
        int t = num2;
        num2 = num1;
        num1 = t;
     }
    if(num1%num2==0)
        return num2;
    else return  GCD(num2,num1%num2);
}
int LCM(int a,int b)//求a。b最小公倍数
{
    int temp_lcm;
    temp_lcm=a*b/GCD(a,b);//最小公倍数等于两数之积除以最大公约数
       return temp_lcm;
}
int main()
{
    int N;
    cin >> N;
    int *arr = new int[N];
    for(int i = 0;i!= N; ++i)
        cin >> arr[i];
    int ans = LCM(arr[0], arr[1]);
    for(int  i = 2; i != N; ++i)
        ans = LCM(ans, arr[i]);
    cout << ans << endl;
    delete []arr;
    return 0;
}