hdoj Least Common Multiple--最大公约数和最小公倍数

本文主要是介绍hdoj Least Common Multiple--最大公约数和最小公倍数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解题思路：求两个数的最小公倍数=两个数相乘，再处理最大公约数。最大公约数用辗转相除术。

最大公约数和最小公倍数说明见下面连接：

https://jingyan.baidu.com/article/0964eca21e03ac8285f53602.html

http://blog.csdn.net/qq_31828515/article/details/51812154

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <stdio.h>using namespace std;
int  gcd(int a,int b){   //最大公约数，辗转相除术if(b==0){return a;} else{return gcd(b,a%b);}
}int main() {int t;int n;int a,tmp;int output;cin >> t;while (t--) {cin >> n;cin >> a;tmp=a;for(int i=1;i<n;i++){cin >> a;tmp=tmp/gcd(tmp,a)*a;  //最小公倍数等于两个数相乘，再处理最大公约数}cout << tmp << endl;}return 0;
}

 

 

这篇关于hdoj Least Common Multiple--最大公约数和最小公倍数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---