最大公约数和最小公倍数问题
编程需要相当扎实的数学基础。
今天笔者要复习的是关于两个数的最大公约数和最小公倍数的问题，同时会收录一些习题进行练习。
最大公约数和最大公倍数的定义
最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。
常用结论
-
如果两个自然数是互质数，那么它们的最大公约数是1，最小公倍数是这两个数的乘积。
例如8和9，它们是互质数，所以（8，9）=1，[8，9]=72。 -
如果两个自然数中，较大数是较小数的倍数，那么较小数就是这两个数的最大公约数，较大数就是这两个数的最小公倍数。
例如18与3，18÷3=6，所以（18，3）=3，[18，3]=18。 -
两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。
例如12和16，（12，16）=4，[12，16]=48，有4×48=12×16，即（12，16）× [12，16]=12×16。
第三个结论在编码中经常用到哦！
用辗转相除法写一个函数求两个数num1,num2的最大公约数为gcd(num1,num2)，那么这两个数的最小公倍数为num1*num2/gcd(num1,num2)
用辗转相除法求最大公约数
两个数的最大公约数是指能同时整除它们的最大正整数。
设两数为x、y，求x和y最大公约数 的步骤如下：
- 令p=max(x,y)，q=min(x,y)，则有p>=q;
- 用p除以q(a≥b)，得 p%q=temp;
- 若 temp =0 ，则(x,y)=q;
- 若 temp !=0 ，则再令p=q,q=temp进行迭代，直到temp=0为止
其最后一个余数为0的除数即为(x,y)的最大公约数。
//辗转相除法求最大公约数
int gcd(int x,int y)
{
int p = max(x,y);
int q = min(x,y);
int temp;
while(q!=0){
temp = p%q;
p = q;
q = temp;
}
return p;
}
根据gcd函数求最小公倍数lcm
根据结论，两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。
即
lcm(x,y) * gcd(x,y) = x*y
所以lcm函数声明及定义如下：
//最小公倍数=x*y/最大公约数
long long lcm(int x,int y)
{
long long ret;
ret = x;
ret = ret*y;
ret = ret/gcd(x,y);
return ret;
}
蓝桥杯训练题：5-1最小公倍数
题目来源
http://lx.lanqiao.cn/problem.page?gpid=T392
问题描述
编写一函数lcm，求两个正整数的最小公倍数。
样例输入
一个满足题目要求的输入范例。
3
5
样例输出
15
与上面的样例输入对应的输出。
数据规模和约定
输入数据中每一个数的范围。
例：两个数都小于65536。
AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
//辗转相除法求最大公约数
long long gcd(int x,int y)
{
int p = max(x,y);
int q = min(x,y);
int temp;
while(q!=0){
temp = p%q;
p = q;
q = temp;
}
return p;
}
//最小公倍数=x*y/最大公约数
long long lcm(int x,int y)
{
long long ret;
ret = x;
ret = ret*y;
ret = ret/gcd(x,y);
return ret;
}
int main()
{
int m,n;
cin>>m>>n;
cout<<lcm(m,n);
return 0;
}
2019蓝桥杯选拔赛：最大公约数和最小公倍数问题
题目来源
http://acm.nefu.edu.cn/problemShow.php?problem_id=2067
Description
输入2个正整数x和y (2<=x<=100000,2<=y<=1000000),求，满足下列条件的p,q的个数？
条件：
p,q是正整数,且p和q的最大公约数是x,最小公倍数是y;
试求:满足条件的所有可能的2个正整数的个数.
Input
输入x和y
Output
输出满足条件的p,q的个数
Sample Input
3 60
Sample Output
4
Hint
对于样例：有4种，
3,60
15，12
12,15
60,3
解题思路
显然min(x,y)<=p,q<=max(x,y)
如果对p,q进行遍历，也即是
int p,q;
int sum = 0;
for(p = min(x,y); p <= max(x,y); p++)
for(q = min(x,y); q <= max(x,y); q++){
if(gcd(p,q) == x && lcm(x,y) == y)
sum++;
}
这样时间复杂度太高，很容易超时，其实笔者试过了，确实Time Limit Exceeded
不妨结合这一结论 p*q = gcd(p,q) * lcm(p,q),可以通过一次遍历求出满足条件p，q的个数。
此题中：
gcd(p,q) = x
lcm(p,q) = y
若已知p时，q要满足条件，要符合pq = gcd(p,q) * lcm(p,q) = xy
所以有q = x*y/p
也即是：
int p,q;
int sum = 0;
for(p = min(x,y); p <= max(x,y); p++){
q = x * y / p;
if(gcd(p,q) == x && lcm(p,q) == y)
sum++;
}
AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
//辗转相除法求最大公约数
long long gcd(int x,int y)
{
int p = max(x,y);
int q = min(x,y);
int temp;
while(q!=0){
temp = p%q;
p = q;
q = temp;
}
return p;
}
//最小公倍数=x*y/最大公约数
long long lcm(int x,int y)
{
long long ret;
ret = x;
ret = ret*y;
ret = ret/gcd(x,y);
return ret;
}
int main()
{
long long x,y;
cin>>x>>y;
long long p,q;
int sum = 0;
for(p=min(x,y);p<=max(x,y);p++){
q = x*y/p;
if(gcd(p,q)==x && lcm(p,q)==y)
sum++;
}
cout<<sum;
return 0;
}