九度1056：最大公约数，题目地址：http://ac.jobdu.com/problem.php?pid=1056
【最大公约数gcd&最小公倍数lcm】 题目描述：
输入两个正整数，求其最大公约数。
- 输入：
- 测试数据有多组，每组输入两个正整数。
- 输出：
- 对于每组输入,请输出其最大公约数。
49 14
样例输出：
7
#include
using namespace std;
/**传统遍历法
*1，如果 x1 = 0 且 x2 = 0则没有；这种情况该题不考虑
*2，如果 x1 = 0 或者 x2 = 0，则最大公约数是不等于0的那个数
*3，依次遍历不大于x1且不大于x2的所有正整数，并依次测试是否满足是a和b的约数；满足的最大的那个正整数即是所求
**/
int gcd1(int x1,int x2){
if(x1 == 0) return x2;
else if(x2 == 0) return x1;
else{
int c,tmp;
c = 1;
tmp = 1;
while(c <= x1 && c <= x2){
if(x1 % c == 0 && x2 % c == 0) tmp = c;
c++;
}
return tmp;
}
}/**欧几里得算法求解 greatest common factor
*1，2种情况与之前的解法相同。在两个数都很大的情况下，要遍历所有比它们小的正整数时间复杂度会很高，用欧几里得算法可以加以简化
*3，因为x1和x2都是由它们的gcd的倍数所组成，所以它们的差值和它们相除的余数依然是它们gcd的倍数
**/
int gcd2(int x1,int x2){
if(x1 == 0) return x2;
else if(x2 == 0) return x1;
else{
int tmp;
while(x2 != 0){
tmp = x1 % x2;
x1 = x2;
x2 = tmp;
}
return x1;
}
} int main(){
int a,b,res;
while(cin >> a >> b){
//res = gcd1(a,b);
res = gcd2(a,b);
cout << res << endl;
}
return 0;
}
九度1438：最小公倍数，题目地址：http://ac.jobdu.com/problem.php?pid=1438
题目描述：
给定两个正整数，计算这两个数的最小公倍数。
- 输入：
- 输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数。
- 输出：
- 对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。
- 样例输入：
-
10 14
- 样例输出：
-
70
/**Least common multiple
*做了最大公约数的问题，求最小公倍数则变得很简单。
*a与b的最小公倍数 = a*b/gcd(a,b)
**/
#include
using namespace std;
//求最大公约数
int gcd(int x1,int x2){
if(x1 == 0) return x2;
else if(x2 == 0) return x1;
else{
int tmp;
while(x2 != 0){
tmp = x1 % x2;
x1 = x2;
x2 = tmp;
}
return x1;
}
}//求最小公倍数
int lcm(int x1,int x2){
if(x1 == 0||x2 == 0) return 0;
else return x1 * x2 / gcd(x1,x2);
}int main(){
int a,b,res;
while(cin >> a >> b){
res = lcm(a,b);
cout << res << endl;
}
return 0;
}
- 九度1439：Least Common Multiple,题目地址：http://ac.jobdu.com/problem.php?pid=1439
- 题目描述：
- The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105.
- 输入：
- Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number of integers in the set and n1 ... nm are the integers. All integers will be positive and lie within the range of a 32-bit integer.
- 输出：
- For each problem instance, output a single line containing the corresponding LCM. All results will lie in the range of a 32-bit integer.
- 样例输入：
-
2 3 5 7 15 6 4 10296 936 1287 792 1
- 样例输出：
-
105 10296
/**
*求n个数的最小公倍数
**/
#include
using namespace std;
//计算两个数的最大公约数
int gcd(int x1,int x2){
if(x1 == 0) return x2;
else if(x2 == 0) return x1;
else{
int tmp;
while(x2 != 0){
tmp = x1 % x2;
x1 = x2;
x2 = tmp;
}
return x1;
}
}
/**
*n:有n组数需要计算 m:该组数有m个数
*res:存储前j个数的最小公倍数；当j = m时，该组数输入完毕，res得到答案：m个数的
*最小公倍数
**/
int main(){
int n,m,i,j,res,tmp;
while(cin >> n){
if(n == 0) break;
for(i = 0;
i < n;
i++){
cin >> m;
res = 1;
for(j = 0;
j < m;
j++){
cin >> tmp;
res = res /gcd(res,tmp) * tmp ;
//比较奇怪的是写成 res = res * tmp / gcd(res,tmp);
在自己电脑上
//测试答案是对的但是提交WA
}
cout << res << endl;
}
}return 0;
}
/**************************************************************
Problem: 1439
User: cherish
Language: C++
Result: Accepted
Time:10 ms
Memory:1520 kb
****************************************************************/ 
