首页 > 代码库 > 杭电 2028 ( Lowest Common Multiple Plus )

杭电 2028 ( Lowest Common Multiple Plus )

2024-09-22 02:59:13   217人阅读

　　链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=2028

　　题目要求：就是求最大公倍数，我百度了一下，最好实现的算法就是：

      公式法
由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即（a，b）×[a，b]=a×b。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。
　　例如，求[18，20]，即得[18，20]=18×20÷（18，20）=18×20÷2=180。求几个自然数的最小公倍数，可以先求出其中两个数的最小公倍数，再求这个最小公倍数与第三个数的最小公倍数，依次求下去，直到最后一个为止。最后所得的那个最小公倍数，就是所求的几个数的最小公倍数。　　　　
　　总结下就是：两数乘积=两数最大公约数*两数最小公倍数。 只不过这次用到的是 两数最小公倍数=两数乘积/两数最大公约数。每两个数个一组依次向后求就可以了。 
　　然后在ac之前犯了个毛病，就是数据类型我全部是int,然后题目要求中有一句：你可以假设最后的输出是一个32位的整数。然后就有个问题：相乘过界。就是过界问题，可能两数相乘会超过 int 的最大界限，所以最好是先除。或者把类型变掉，我选择后者。
#include <iostream>
#include<math.h>
#include <iomanip>
#include<cstdio>
#include<string>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<stdlib.h>
#include<iterator>
using namespace std;

int gcd(int a,int b)
{
    int big=a;
    int smal=b;
    int ck;
    if(big<smal)
    {
        ck=a;
        a=b;
        b=a;
    }
    int temp;
    while(smal>0)
    {
        temp=big%smal;
        big=smal;
        smal=temp;
    }
    return big;
}

unsigned int gys(unsigned int a,unsigned int b)
{
    unsigned int kk;
    unsigned int ak=a;
    unsigned int bk=b;
    kk=ak*bk/gcd(ak,bk);
    return kk;
}

int main()
{

    int n;
    while(cin>>n)
    {
    unsigned int *p;
    p=new unsigned int[n];

    for(int i=0;i<n;i++)
    {
        cin>>p[i];
    }

    int unsigned max_gys=p[0];

    for(int j=0;j<n-1;j++)
    {
        max_gys=gys(max_gys,p[j+1]);
    }
    cout<<max_gys<<endl;

    delete []p;
    }



    return 0;
}

 

　　

杭电 2028 ( Lowest Common Multiple Plus )


联系
我们