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

杭电 2028 ( Lowest Common Multiple Plus )

  链接: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 )