1019(C++)

计算n个数的最小公倍数,可用欧几里得算法计算两个数字的最大公约数,再计算两个数最小公倍数

有了2个数最小公倍数算法就简单了,即为:计算第一和第二个数得到最小公倍数lc,再计算lc和第三个数最小公倍数......

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
inline int lcm(int a,int b);
int main()
{
 int N, n,a, i;
 cin >> N;
 while (N--)
 {
  cin >> n;
  vector<int>v;
  for (i = 0; i < n&&cin >> a; i++)
   v.push_back(a);
  if (n == 1)
  {
   cout << v[0] << endl;
   continue;
  }
  int lc = lcm(v[0], v[1]);
  for (i=2; i < n; i++)
   lc = lcm(lc, v[i]);
  cout << lc << endl;
 }
 return 0;
}
inline int lcm(int a, int b)
{
 int r,ra=a,rb=b;  //ra,rb记录初始传入是的a,b的值
 if (a<b)
  swap(a, b);
 while (a%b!= 0)
 {
  r = a%b;
  a = b;
  b = r;
 }
 int lc = ra*(rb / b);
 return lc;
}

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。