文章目錄
- Contest100000589 - 《算法筆記》5.2小節——數學問題->最大公約數與最小公倍數
- 5.2 最大公約數與最小公倍數
-
- 5.2.1 最大公約數
-
- 例題Codeup1818:最大公約數
- 5.2.2最小公倍數
- Codeup習題
-
- Contest100000589 - 《算法筆記》5.2小節——數學問題->最大公約數與最小公倍數
- 2136Problem ALeastCommonMultiple
- 總結下：
Contest100000589 - 《算法筆記》5.2小節——數學問題->最大公約數與最小公倍數
5.2 最大公約數與最小公倍數
5.2.1 最大公約數
//5.2.1最大公約數
int gcd(int a,int b)
{
if(b == 0) return a;
else return gcd(b,a%b);
}
例題Codeup1818:最大公約數
題目連結：http://codeup.cn/problem.php?id=1818
//1818: 最大公約數
#include <iostream>
//5.2最大公約數與最小公倍數
int gcd(int a,int b)//最大公約數
{
int temp;
if(a < b)
{
temp = a;
a = b;
b = temp;
}
if(b == 0) return a;
else return gcd(b,a%b);
}
int lcm(int a,int b)//最小公倍數
{
int temp;
if(a < b)
{
temp = a;
a = b;
b = temp;
}
return a/(gcd(a,b))*b;
}
5.2.2最小公倍數
Codeup習題
Contest100000589 - 《算法筆記》5.2小節——數學問題->最大公約數與最小公倍數
題目連結：http://codeup.cn/contest.php?cid=100000589
2136Problem ALeastCommonMultiple
題目連結：http://codeup.cn/problem.php?cid=100000589&pid=0
//2136 Problem A Least Common Multiple
//沒有考慮兩數誰大誰小的問題？
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
//5.2最大公約數與最小公倍數
int gcd(int a,int b)//最大公約數
{
int temp;
if(a < b)
{
temp = a;
a = b;
b = temp;
}
if(b == 0) return a;
else return gcd(b,a%b);
}
int lcm(int a,int b)//最小公倍數
{
int temp;
if(a < b)
{
temp = a;
a = b;
b = temp;
}
return a/(gcd(a,b))*b;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int m,a,b;
cin>>m>>a;
m--;//将第一輸入的數作為初始最小公倍數，因而共處理m-1次，也即m個數共m-1對
while(m--)
{
cin>>b;
a = lcm(a,b);
}
cout<<a<<endl;
}
return 0;
}
總結下：
最大公約數與最小公倍數公式固定，gcd(b,a%b),lcm=a/(gcd(a,b))*b;
注意前提是a>=b，若a<b需要互換位置