#include <assert.h>

template <class T>
__inline void Swap(T &a, T &b)
{
 T t;
 t = a;
 a = b;
 b = t;
}

// 辗转相除法求最大公约数
template <class T>
__inline T GCD(T m, T n)
{
 assert(m >= 0 && n >= 0);

 if(m == 0)
  return n;

 if(n == 0)
  return m;
 
 if(m < n)
 {
  Swap(m, n);
 }

 T  d = m % n;
 while(d > 0)
 {
  m = n;
  n = d;
  d = m % n;
 }

 return n;
}

#include <stdio.h>
#include <time.h>
#include <conio.h>
int main()
{
 long  x[100];
 long  n;

 printf("Input the number of numbers: ");
 scanf("%d", &n);
 printf("Input %d numbers: ", n);
 
 for(int i=0; i<n; ++i)
  scanf("%d", x+i);

 long  t;
 t = clock();

 __int64  lcm = x[0];
 long  gcd = 1;
 for(i=1; i<n; ++i)
 {
  gcd = GCD((long)lcm, x[i]);
  lcm *= x[i] / gcd;
 }
  
 t = clock()-t;

 printf("\nThe least multiple these numbers is %I64d\n", lcm);
 printf("Time cost is %ld ms.\n", t);
 getch();
 return 0;
}

评论