Lowest Common Multiple Plus
- Time Limit: 2000/1000ms (Java/Others)
- Problem Description:
求 n 个数的最小公倍数.
Input:
输入包含多个测试实例, 每个测试实例的开始是一个正整数 n(2<=n<=100), 然后是 n 个正整数 (数字均大于 0).
Output:
为每组测试数据输出它们的最小公倍数, 每个测试实例的输出占一行. 你可以假设最后的输出是一个 64 位的整数.
- Sample Input:
- 2 3 4 3 23 45 2
- Sample Output:
- 12
- 2070
解题思路: 求 n 个数的最小公倍数,(其中 n>=2), 先求出这两个数的最大公约数, 再利用这两个数的乘积等于这两个数的最小公倍数和最大公约数的乘积即可求出 n 个数的最小公倍数.
设两个数是 a,b 最大公约数是 p, 最小公倍数是 q, 则 ab=pq, 即 q=ab/p(q=a/p*b 或 q=b/p*a). 本题就是根据这样的关系来求最小公倍数的.
AC 代码:
- #include<iostream>
- using namespace std;
- typedef long long LL ;
- LL gcd(LL a,LL b) // 求两个数的最大公约数
- {
- return b ? gcd(b,a%b):a;
- }
- LL lcm(LL m,LL g) // 求两个数的最小公倍数
- {
- return m/gcd(m,g)*g;
- }
- int main()
- {
- int n;
- LL lowest,q;
- while(cin>>n){
- cin>>q>>lowest;
- lowest=lcm(q,lowest);
- n-=2;
- while(n--){
- cin>>q;
- lowest=lcm(q,lowest);
- }
- cout<<lowest<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2557652.html