【数论】 —— 最大公因数与最小公倍数
- 世界杯冠军奖金
- 2025-05-03 21:05:41
- 3266
最大公因数与最小公倍数
这一章内容比较少，主要讲的是最大公因数的几种求法。
最大公因数
定义
在两个数的公因数中最大的那个叫做这两个数的最大公因数。
我们一般用
gcd
(
a
,
b
)
\gcd(a,b)
gcd(a,b) 来表示
a
a
a，
b
b
b 两数的最大公因数。
接下来，我给大家介绍
4
4
4 种求最大公因数的方法。
穷举法
顾名思义，即暴力枚举：从两个数中较小的一个开始从大到小枚举，遇到的第一个可以同时整除这两个数的数就是它们的最大公因数。
至于为什么要从较小的一个开始枚举，因为两个数的公因数只可能小于等于较小的那个数。
时间复杂度：
O
(
min
(
a
,
b
)
)
O(\min(a,b))
O(min(a,b))。
代码
inline int gcd(int a , int b) {
int x = min(a , b);
for(register int i = x;i >= 1;i --)
if(a % i == 0 && b % i == 0)
return i;
}
辗转相除法
定义
辗转相除法，又称欧几里得算法，是一种用来求最大公因数的算法。其算法流程主要基于这么一个式子：
gcd
(
a
,
b
)
=
gcd
(
b
,
a
m
o
d
b
)
\gcd(a,b)=\gcd(b,a\bmod b)
gcd(a,b)=gcd(b,amodb)。当
a
m
o
d
b
=
0
a\bmod b=0
amodb=0 时，便可以得到两数的最大公因数，即
gcd
(
b
,
a
m
o
d
b
)
\gcd(b,a\bmod b)
gcd(b,amodb) 中的
b
b
b。
由这个式子，我们可以想到一种递归求最大公因数的写法：
代码
int gcd(int a , int b) {
if(!b)
return a;
return gcd(b , a % b);
}
当然，也可以把这个过程改写成一个循环：
inline int gcd(int a , int b) {
int r = a % b;
while(r) {
a = b;
b = r;
r = a % b;
}
return b;
}
时间复杂度均为：
O
(
log
max
(
a
,
b
)
)
O(\log \max(a,b))
O(logmax(a,b))。
辗转相除法的证明
下面给出证明：
设
d
d
d 是
a
a
a，
b
b
b 的任意一个公因数且
a
>
b
a > b
a>b。
则必有：
a
=
k
b
+
r
a=kb+r
a=kb+r；
移项得：
r
=
a
−
k
b
r=a-kb
r=a−kb；
两边同时除以
d
d
d 得：
r
d
=
a
d
−
k
b
d
\frac{r}{d}=\frac{a}{d}-\frac{kb}{d}
dr=da−dkb；
因为
d
d
d 是
a
a
a 与
b
b
b 的公因数，所以
d
∣
a
d\mid a
d∣a 并且
d
∣
b
d\mid b
d∣b。由此得到：
d
∣
r
d\mid r
d∣r。
而
r
=
a
m
o
d
b
r=a\bmod b
r=amodb。
所以，
d
d
d 既是
a
a
a，
b
b
b 的公因数，也是
b
b
b，
a
m
o
d
b
a\bmod b
amodb 的公因数。
现在我们证出
(
a
,
b
)
(a,b)
(a,b) 与
(
b
,
a
m
o
d
b
)
(b,a\bmod b)
(b,amodb) 的公因数相等，而由
d
d
d 的任意性得
d
d
d 可为
a
a
a 与
b
b
b 的最大公因数。故得证。
更相减损法
定义
更相减损法，即把两数不断相减，直到两数相等。其实主要思想和辗转相除法类似。
具体算法流程是：
试求
a
a
a，
b
b
b 两数的最大公因数。
若
2
∣
a
2\mid a
2∣a 且
2
∣
b
2\mid b
2∣b，则先将两数所含的
2
2
2 给除掉。
接着，我们不断用大数减小数，直到两数相等。此时相等的两数乘上约掉的
2
2
2 即为原本两数的最大公因数。
用公式表达就是：
gcd
(
2
a
,
2
b
)
=
2
gcd
(
a
,
b
)
\gcd(2a,2b)=2\gcd(a,b)
gcd(2a,2b)=2gcd(a,b)。
a
≥
b
a\ge b
a≥b，
gcd
(
a
,
b
)
=
gcd
(
a
,
a
−
b
)
=
gcd
(
b
,
a
−
b
)
\gcd(a,b)=\gcd(a,a-b)=\gcd(b,a-b)
gcd(a,b)=gcd(a,a−b)=gcd(b,a−b)。
我们发现，其实第一步可以省略，直接执行第二步即可。
时间复杂度与辗转相除法一样：
O
(
log
max
(
a
,
b
)
)
O(\log \max(a,b))
O(logmax(a,b))。
代码
代码实现比较简单：
inline int gcd(int a , int b) {
while(a != b) {
if(a > b)
a = a - b;
else
b = b - a;
}
return a;
}
更相减损法的证明
第一个公式十分好证：
因为
2
a
2a
2a 与
2
b
2b
2b 均为
2
2
2 的倍数，所以
2
2
2 必是
2
a
2a
2a 与
2
b
2b
2b 的一个公因数，所以最大公因数中包含
2
2
2。故可以将其提出。
接下来我们来证明第二个公式：
设
d
=
gcd
(
a
,
b
)
d=\gcd(a,b)
d=gcd(a,b)。
则
a
a
a 与
b
b
b 必能表示成：
a
=
k
1
d
a=k_1d
a=k1d，
b
=
k
2
d
b=k_2d
b=k2d。
令
a
>
b
a > b
a>b，所以
a
−
b
=
d
(
k
1
−
k
1
)
a-b=d(k1-k1)
a−b=d(k1−k1)，可以得到
d
∣
(
a
−
b
)
d\mid (a-b)
d∣(a−b)。
由此可得：
gcd
(
a
,
b
)
=
gcd
(
a
,
a
−
b
)
=
gcd
(
b
,
a
−
b
)
\gcd(a,b)=\gcd(a,a-b)=\gcd(b,a-b)
gcd(a,b)=gcd(a,a−b)=gcd(b,a−b)。 故得证。
二进制算法
对于处理数位较少的数的最大公因数，使用辗转相除法就可以了，但当数位达到上百位时便需要用到高精度。此时，辗转相除法就不那么适用了。对于这类问题，我们可以用支持高精度的二进制算法。
算法流程如下：
若
a
=
b
a=b
a=b，则
gcd
(
a
,
b
)
=
a
\gcd(a,b)=a
gcd(a,b)=a；
否则，分情况讨论：
若
a
a
a 和
b
b
b 均为偶数，则：
gcd
(
a
,
b
)
=
2
×
gcd
(
a
÷
2
,
b
÷
2
)
\gcd(a,b)=2\times\gcd(a\div 2,b\div 2)
gcd(a,b)=2×gcd(a÷2,b÷2)。
若
a
a
a 为偶数，
b
b
b 为奇数，则
gcd
(
a
,
b
)
=
gcd
(
a
÷
2
,
b
)
\gcd(a,b)=\gcd(a\div 2,b)
gcd(a,b)=gcd(a÷2,b)。
若
a
a
a 与
b
b
b 均为奇数，则
gcd
(
a
,
b
)
=
gcd
(
a
−
b
,
b
)
\gcd(a,b)=\gcd(a-b,b)
gcd(a,b)=gcd(a−b,b)。
最终答案即是第一个操作中被约掉的
2
2
2 乘操作
3
3
3 的结果。
其实二进制算法和更相减损法十分相似。这里就不给证明了。
代码
这里给出一个完整的高精度最大公因数的代码：
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
string s1 , s2;
int a[3005] , b[3005] , c[3005];
int len1 , len2;
inline void div1(int a[]) {
int r = 0;
for(register int i = len1;i >= 1;i --) {
a[i] = a[i] + r * 10;
r = a[i] % 2;
a[i] /= 2;
}
while(!a[len1] && len1 > 1)
len1 --;
return;
}
inline void div2(int b[]) {
int r = 0;
for(register int i = len2;i >= 1;i --) {
b[i] = b[i] + r * 10;
r = b[i] % 2;
b[i] /= 2;
}
while(!b[len2] && len2 > 1)
len2 --;
return;
}
inline bool equal(int a[] , int b[]) {
if(len1 != len2)
return false;
for(register int i = 1;i <= len1;i ++)
if(a[i] != b[i])
return false;
return true;
}
inline void poww(int a[] , int x) {
for(register int i = 1;i <= 3000;i ++)
a[i] *= x;
for(register int i = 1;i <= 3000;i ++) {
a[i + 1] += a[i] / 10;
a[i] %= 10;
}
len1 = 3000;
while(!a[len1] && len1 > 1)
len1 --;
for(register int i = len1;i >= 1;i --)
cout << a[i];
return;
}
inline bool bigger(int a[] , int b[]) {
if(len2 < len1)
return false;
if(len2 > len1)
return true;
for(register int i = len1;i >= 1;i --)
if(b[i] > a[i])
return true;
else if(a[i] > b[i])
return false;
return false;
}
inline void change(int a[] , int b[]) {
for(register int i = 1;i <= len1;i ++)
c[i] = a[i];
for(register int i = 1;i <= len2;i ++)
a[i] = b[i];
for(register int i = 1;i <= len1;i ++)
b[i] = c[i];
int k = len1;
len1 = len2;
len2 = k;
for(register int i = 3000;i > len2;i --)
b[i] = 0;
for(register int i = 3000;i > len1;i --)
a[i] = 0;
return;
}
inline void mi(int a[] , int b[]) {
for(register int i = 1;i <= len1;i ++)
a[i] = a[i] - b[i];
for(register int i = 1;i <= len1;i ++)
if(a[i] < 0) {
a[i] += 10;
a[i + 1] --;
}
while(!a[len1] && len1 > 1)
len1 --;
return;
}
inline int ksm(int x) {
int result = 1 , base = 2;
while(x > 0) {
if(x & 1)
result = result * base;
x >>= 1;
base = (base * base);
}
return result;
}
//精髓部分
inline void gcd(int a[] , int b[]) {
int i , j;
for(i = 0;a[1] & 0;i ++)
div1(a);
for(j = 0;b[1] & 0;j ++)
div2(b);
if(i > j)
i = j;
int k = ksm(i);
while(true) {
if(equal(a , b)) {
poww(a , k);
exit(0);
}
if(bigger(a , b))
change(a , b);
mi(a , b);
while(a[1] & 0)
div1(a);
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> s1 >> s2;
len1 = s1.size();
len2 = s2.size();
for(register int i = 0;i < len1;i ++)
a[len1 - i] = s1[i] - '0';
for(register int i = 0;i < len2;i ++)
b[len2 - i] = s2[i] - '0';
gcd(a , b);
return 0;
}
c++ 自带函数
在这么多求最大公因数的算法中，应用的比较的多的就只有辗转相除法。但其实 c++ 内部也有自带的求最大公因数的函数，即：__gcd()函数，用法和手写的一样。若要求
a
a
a 与
b
b
b 的最大公因数，代码应为：cout << __gcd(a,b)。
最小公倍数
定义
两数的公倍数中最小的那个数被称作这两个数的最小公倍数。
我们一般用
L
C
M
(
a
,
b
)
LCM(a,b)
LCM(a,b) 表示两个数的最小公倍数。
最小公倍数的求法
易得：
L
C
M
(
a
,
b
)
=
a
÷
gcd
(
a
,
b
)
×
b
LCM(a,b)=a\div \gcd(a,b)\times b
LCM(a,b)=a÷gcd(a,b)×b。
这个公式十分容易得到，这里就不给推导过程了。
个人建议先除以
gcd
(
a
,
b
)
\gcd(a,b)
gcd(a,b) 再乘
b
b
b，以防止
a
a
a 和
b
b
b 过大，然后相乘溢出。
代码
int gcd(int a , int b) {
if(!b)
return a;
return gcd(b , a % b);
}
inline int lcm(int a , int b) {
return a / gcd(a , b) * b;
}
