第四章 数学知识（一）
如无特殊说明，所有数均为正整数
质数
质数： 针对所有大于 1 1 1 的自然数来说，如果只包含 1 1 1 和本身 这两个约数，就被称为质数，或者叫素数；否则被称为 合数.
所有 ≤ 1 leq 1 ≤1 的数 既不是质数，也不是合数.
约数： 若 d d d 能整除 n n n，或者说 n n n 能被 d d d 整除，或者说 n n n 是 d d d 的倍数，则称 d d d 为 n n n 的约数或因子，记作 d ∣ n d|n d∣n.
1. 质数的判定——试除法 AcWing 866. 试除法判定质数若 d d d 为质数，则称 d d d 为质因子.
原题链接
给定 n n n 个正整数 a i a_i ai，判定每个数是否是质数。
输入格式
第一行包含整数 n n n。
接下来 n n n 行，每行包含一个正整数 a i a_i ai。
输出格式
共 n n n 行，其中第 i i i 行输出第 i i i 个正整数 a i a_i ai
是否为质数，是则输出 Yes，否则输出 No。
数据范围
1
≤
n
≤
100
1≤n≤100
1≤n≤100,
1
≤
a
i
≤
2
31
−
1
1≤a_i≤2^{31}-1
1≤ai≤231−1
输入样例：
2 2 6
输出样例：
Yes No
yxc’s Solution时/空限制： 1s / 64MB
来源： 模板题
算法标签：数学知识 质数 试除法
判断两个条件：
是不是大于 1 1 1；是不是只包含 1 1 1 和它本身 两个约数.
bool is_prime(int n){
if(n<2) return false;
for(int i=2;i
时间复杂度为
O
(
n
)
O(n)
O(n).可以对如上代码进行优化.性质：如果
d
∣
n
d|n
d∣n （
d
d
d 能整除
n
n
n），那么显然
n
d
∣
n
frac{n}{d}|n
dn∣n，也就是说，约数总是成对出现的（
d
d
d,
n
d
)
frac{n}{d})
dn).
例如，
n
=
12
n=12
n=12，则
12
3
=
4
frac{12}{3}=4
312=4，同理有
12
4
=
3
frac{12}{4}=3
412=3.
所以在枚举时，只需要枚举每对之中较小的那个，则有
d
≤
n
d
→
d
2
≤
n
→
d
≤
n
d leq frac{n}{d} to d^2 leq n to d leq sqrt n
d≤dn→d2≤n→d≤n
；
可以发现，
d
d
d 只需要枚举到
n
sqrt n
n
即可，时间复杂度就可以降到
O
(
n
)
O(sqrt n)
O(n
).
不推荐写成 for(int i=1;i<=sqrt(n);++i，因为每次循环都会求一次
n
sqrt n
n
的值；
也不推荐写成 for(int i=1;i*i<=n;++i，因为当
n
n
n 接近于 int 的最大值时，i 是存在溢出风险的.
#include
#include
#include
using namespace std;
bool is_prime(int n){
if(n<2) return false;
for(int i=2;i<=n/i;++i)
if(n%i==0) return false;
return true;
}
int main(){
int n,a;
scanf("%d",&n);
while(n--){
scanf("%d",&a);
if(is_prime(a)) puts("Yes");
else puts("No");
}
return 0;
}
2. 分解质因数——试除法
AcWing 867. 分解质因数
原题链接
给定
n
n
n 个正整数
a
i
a_i
ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数
n
n
n。
接下来
n
n
n 行，每行包含一个正整数
a
i
a_i
ai。
输出格式
对于每个正整数
a
i
a_i
ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1
≤
n
≤
100
1≤n≤100
1≤n≤100,
1
≤
a
i
≤
2
×
1
0
9
1≤a_i≤2×10^9
1≤ai≤2×109
输入样例：
2
6
8
输出样例：
2 1
3 1
2 3
时/空限制： 1s / 64MB
来源： 模板题
算法标签：数学知识 分解质因数 试除法
yxc’s Solution
从小到大枚举
n
n
n 的所有约数，时间复杂度
O
(
n
)
O(n)
O(n)；
void divide(int n){
for(int i=2;i<=n;++i)
if(n%i==0){ //若成立，i 一定是质数
int s=0;
while(n%i==0){
n/=i;
++s;
}
printf("%d %dn",i,s);
}
puts("");
}
Q：不应该从小到大枚举所有质因数吗？为什么会是从小到大枚举所有的数？会枚举到合数的，会不会有问题呢？
A：其实是没有问题的，分解质因数的结果确实应为
n
=
P
1
c
1
⋯
P
k
c
k
n=P_1^{c_1}cdots P_k^{c_k}
n=P1c1⋯Pkck，其中
P
i
P_i
Pi 应该是质数；
但是当代码枚举到
i
i
i 时，就意味着 把
2
∼
i
−
1
2 sim i-1
2∼i−1 当中所有的质因子都除干净了，即
n
n
n 中已经不包含任何
2
∼
i
−
1
2 sim i-1
2∼i−1 中的质因子；
如果此时
n
%
i
=
0
n%i=0
n%i=0，说明
n
n
n 是
i
i
i 的倍数，结合
n
n
n 当中不包含任何
2
∼
i
−
1
2 sim i-1
2∼i−1 当中的质因子，所以
i
i
i 当中也不包含
2
∼
i
−
1
2 sim i-1
2∼i−1 当中的质因子，故
i
i
i 就一定为质数.
性质：
n
n
n 中最多只包含一个大于
n
sqrt n
n
的质因子.
证明：假设
n
n
n 中包含两个大于
n
sqrt n
n
的质因子
P
i
,
P
j
P_i,P_j
Pi,Pj，则
P
i
∗
P
j
>
n
∗
n
=
n
P_i * P_j> sqrt n * sqrt n=n
Pi∗Pj>n
∗n
=n，矛盾，则两个及以上个都不应该成立.
所以枚举时，可以先将小于
n
sqrt n
n
的质因子枚举出来；如果最后
n
>
1
n>1
n>1，说明最后剩下这个数就是
n
n
n 当中大于
n
sqrt n
n
的质因子；
时间复杂度
O
(
n
)
O(sqrt n)
O(n
).
#include
#include
#include
#include
using namespace std;
void divide(int n){
for(int i=2;i<=n/i;++i)
if(n%i==0){
int s=0;
while(n%i==0){
n/=i;
++s;
}
printf("%d %dn",i,s);
}
if(n>1) printf("%d 1n",n);
puts("");
}
int main(){
int n,a;
scanf("%d",&n);
while(n--){
scanf("%d",&a);
divide(a);
}
return 0;
}
值得注意的是，虽然 质数的判定 和 分解质因数 的代码的时间复杂度都是
n
sqrt n
n
，但是还是有区别的：
质数的判定的代码的时间复杂度一定是
n
sqrt n
n
，因为 for 循环一定会循环
n
sqrt n
n
次；分解质因数的代码的时间复杂度不一定是
n
sqrt n
n
，如
n
=
2
k
n=2^k
n=2k 时，for 循环只会循环
1
1
1 次；所以其时间复杂度 最好是
O
(
log
n
)
O(log n)
O(logn)，最坏是
O
(
n
)
O(sqrt n)
O(n
).
3. 筛法
AcWing 868. 筛质数
原题链接
给定一个正整数
n
n
n，请你求出
1
∼
n
1 sim n
1∼n 中质数的个数。
输入格式
共一行，包含整数
n
n
n。
输出格式
共一行，包含一个整数，表示
1
∼
n
1∼n
1∼n 中质数的个数。
数据范围
1
≤
n
≤
1
0
6
1≤n≤10^6
1≤n≤106
输入样例：
8
输出样例：
4
时/空限制： 0.2s / 64MB
来源： 模板题
算法标签：数学知识 质数 线性筛法 筛法求素数
yxc’s Solution
朴素做法
首先先把所有数写到一个数表当中：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
随后从前往后看，将每个数所有的倍数都删掉：
先把
2
2
2 的所有倍数删掉.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
再把
3
3
3 的所有倍数删掉.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
再把
4
4
4 的所有倍数删掉.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
再把
5
5
5 的所有倍数删掉.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
以此类推……
这样筛完之后，所有剩下的数都是质数.
因为对一个数
P
P
P 而言，如果它没有被删掉，就意味着
P
P
P 不是
2
∼
P
−
1
2 sim P-1
2∼P−1 中任何一个数的倍数，换言之即为
2
∼
P
−
1
2 sim P-1
2∼P−1 中没有
P
P
P 的约数，所以
P
P
P 是一个质数.
void get_primes(int n){
for(int i=2;i<=n;++i){
if(!st[i]) primes[cnt++]=i;
for(int j=i+i;j<=n;j+=i) st[j]=true;
}
}
时间复杂度分析：代码的运算次数为
n
2
+
n
3
+
n
4
+
⋯
+
n
n
=
n
(
1
2
+
1
3
+
⋯
+
1
n
)
≈
n
ln
n
<
n
log
n
frac{n}{2}+frac{n}{3}+frac{n}{4}+cdots+frac{n}{n}=n(frac{1}{2}+frac{1}{3}+cdots+frac{1}{n}) approx n ln n < n log n
2n+3n+4n+⋯+nn=n(21+31+⋯+n1)≈nlnn
有调和级数
1
+
1
2
+
1
3
+
⋯
+
1
n
1+frac{1}{2}+frac{1}{3}+cdots+frac{1}{n}
1+21+31+⋯+n1，且存在
lim
n
→
∞
1
+
1
2
+
1
3
+
⋯
+
1
n
=
ln
n
+
C
lim_{ntoinfty}1+frac{1}{2}+frac{1}{3}+cdots+frac{1}{n}=ln n+C
limn→∞1+21+31+⋯+n1=lnn+C， 其中
ln
n
=
log
e
n
ln n=log_e n
lnn=logen，而
C
C
C 是一个欧拉常数，
C
≈
0.577
C approx 0.577
C≈0.577，且有
log
e
n
<
log
2
n
log_e n < log_2 n
logen
故时间复杂度可以记成
O
(
n
log
n
)
O(n log n)
O(nlogn).
埃氏筛法
可以发现，这里并不需要把每一个数的所有倍数全部删掉，这里可以只把所有质数的倍数全部删掉.
为什么呢？如果留下
P
P
P，说明
P
P
P 是一个质数；可以发现其实并不需要把
2
∼
P
−
1
2 sim P-1
2∼P−1 都枚举一遍判断其是否为
P
P
P 的约数，而只需要把
2
∼
P
−
1
2 sim P-1
2∼P−1 当中的质数判断一下就可以了.
所以只需要删掉质数的倍数即可.
void get_primes(int n){
for(int i=2;i<=n;++i)
if(!st[i]){
primes[cnt++]=i;
for(int j=i+i;j<=n;j+=i) st[j]=true;
}
}
时间复杂度约为
O
(
n
ln
n
ln
n
)
≈
O
(
n
)
O(frac{n ln n}{ln n})approx O(n)
O(lnnnlnn)≈O(n).
质数分布定理：
1
∼
n
1 sim n
1∼n 中有大约
n
ln
n
frac{n}{ln n}
lnnn 个质数.
这样整个代码就可以少算
ln
n
ln n
lnn 倍，但真实的时间复杂度应该近似于
O
(
n
log
log
n
)
O(n log log n)
O(nloglogn).
优化完后的筛法被称为 埃氏筛法.
线性筛法
思路基本同上，即 将合数用其质因子筛掉.
void get_primes(int n){
for(int i=2;i<=n;++i){
if(!st[i]) st[i]=primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;++j){
st[primes[j]*i]=primes[j];
if(i%primes[j]==0) break;
}
}
}
st[i] 中储存的是 i 的最小质因子.
线性筛法在
1
0
7
10^7
107 的数据规模下，比埃氏筛法 快一倍左右；在
1
0
6
10^6
106 的数据规模下，时间效率是差不多的.
线性筛法的核心思路：每一个数
n
n
n，只会被它的最小质因子筛掉.若 i%primes[j]==0 ， 由于质数是从小到大枚举的，说明 primes[j] 一定是 i 的最小质因子，也就是说 primes[j] 一定是 i*primes[j] 的最小质因子；若 i%primes[j]!=0，由于质数是从小到大枚举的，说明 primes[j] 一定是小于 i 的所有质因子的，所以 prime[j] 也一定是 i*prime[j] 的最小质因子；因为合数一定存在最小质因子，所以每个合数都会被筛掉；又因为每个合数都只会被自己的最小质因子筛掉，所以这个算法是线性的；时间复杂度为
O
(
n
)
O(n)
O(n).
《信息奥赛一本通·提高篇》中的写法是这样的：
void get_primes(int n){
for(int i=2;i<=n;++i){
if(!st[i]) st[i]=primes[cnt++]=i;
for(int j=0;jst[i] || primes[j]>n/i) break;
st[primes[j]*i]=primes[j];
}
}
}
可以通过不同的写法来加深对于代码顺序和算法原理的理解.
j
#include
#include
#include
using namespace std;
const int N=1000010;
int primes[N],cnt,st[N];
void get_primes(int n){
for(int i=2;i<=n;++i){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;++j){
st[primes[j]*i]=primes[j];
if(i%primes[j]==0) break;
}
}
}
int main(){
int n;
scanf("%d",&n);
get_primes(n);
printf("%d",cnt);
return 0;
}
实际应用中，用的比较多的还是线性筛法，埃氏筛法的思想是比较重要的.
约数
1.试除法求一个数的所有约数
AcWing 869. 试除法求约数
题目描述
给定
n
n
n 个正整数
a
i
a_i
ai，对于每个整数
a
i
a_i
ai，请你按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数
n
n
n。
接下来
n
n
n 行，每行包含一个整数
a
i
a_i
ai。
输出格式
输出共
n
n
n 行，其中第
i
i
i 行输出第
i
i
i 个整数
a
i
a_i
ai 的所有约数。
数据范围
1
≤
n
≤
100
1≤n≤100
1≤n≤100,
2
≤
a
i
≤
2
×
1
0
9
2≤ai≤2×10^9
2≤ai≤2×109
输入样例：
2
6
8
输出样例：
1 2 3 6
1 2 4 8
时/空限制： 1s / 64MB
来源： 模板题
算法标签：数学知识 约数 试除法
yxc’s Solution
算法同样有一个优化：
基于性质：如果
d
∣
n
d|n
d∣n （
d
d
d 能整除
n
n
n），那么显然
n
d
∣
n
frac{n}{d}|n
dn∣n，也就是说，约数总是成对出现的（
d
d
d,
n
d
)
frac{n}{d})
dn)；
所以也只需要枚举到
n
sqrt n
n
即可.
#include
#include
#include
#include
using namespace std;
vectorget_divisors(int n){
vectorres;
for(int i=1;i<=n/i;++i)
if(n%i==0){
res.push_back(i);
if(i!=n/i) res.push_back(n/i);
}
sort(res.begin(),res.end());
return res;
}
int main(){
int n,a;
scanf("%d",&n);
while(n--){
scanf("%d",&a);
auto res=get_divisors(a);
for(auto t:res) printf("%d ",t);
puts("");
}
return 0;
}
时间复杂度为
O
(
n
)
O(sqrt n)
O(n
).
做数论题时，很重要的事情就是需要每步都算一算时间复杂度，只有每一步都不超时，才可以做.
Q：那排序的时间复杂度呢？
A：一个数
n
n
n 的约数个数，用类似筛法的过程来看，即
1
∼
n
1 sim n
1∼n 当中总共约数个数（即每个数有多少约数） 和
1
∼
n
1 sim n
1∼n 当中总共倍数个数（即有多少数是当前数的倍数） 是相同的；
那么
1
1
1 的倍数有
n
n
n 个、
2
2
2 的倍数 有
n
2
frac{n}{2}
2n 个、……、
n
n
n 的倍数有
n
n
frac{n}{n}
nn 个，故总共有
n
ln
n
≈
n
log
n
n ln n approx n log n
nlnn≈nlogn 个倍数，那么平均下来每个数大约有
log
n
log n
logn 个约数.
故排序的时间复杂度为
O
(
log
n
log
log
n
)
O(log n log log n)
O(lognloglogn)，其一般是小于
O
(
n
)
O(sqrt n)
O(n
) 的；故在算时间复杂度时，只取
O
(
n
)
O(sqrt n)
O(n
).
int 范围内，约数个数最多的一个数，其约数个数大约在
1500
1500
1500 个左右.
根据约数的性质，可以发现约数是成对出现的，所以一个数的约数个数的上限为
2
n
2sqrt n
2n
.
2.约数个数与约数之和
约数个数
约数个数是基于算数基本定理的：
算数基本定理：任何一个大于
1
1
1 的正整数都能唯一分解为有限个质数的乘积，可写作：
N
=
P
1
c
1
P
2
c
2
⋯
P
m
c
m
N=P_1^{c_1}P_2^{c_2}cdots P_m^{c_m}
N=P1c1P2c2⋯Pmcm，其中
c
i
c_i
ci 都是正整数，
P
i
P_i
Pi 都是质数且满足
P
1
<
P
2
<
⋯
<
P
m
P_1 < P_2 < cdots < P_m
P1 则约数个数即为
(
c
1
+
1
)
(
c
2
+
1
)
⋯
(
c
m
+
1
)
(c_1+1)(c_2+1)cdots (c_m+1)
(c1+1)(c2+1)⋯(cm+1).
因为对于
n
n
n 的任意一个约数
d
=
P
1
β
1
P
2
β
2
⋯
P
m
β
m
d=P_1^{beta_1}P_2^{beta_2}cdots P_m^{beta_m}
d=P1β1P2β2⋯Pmβm，都有
0
≤
β
i
≤
c
i
0 leq beta_i leq c_i
0≤βi≤ci，并且每一项的指数
β
i
beta_i
βi 不同，则约数
d
d
d 也不同；故
d
d
d 的个数和
β
1
∼
β
k
beta_1 sim beta_k
β1∼βk 的取法的个数是一样的.
约数之和
约数之和为
(
P
1
0
+
P
1
1
+
⋯
+
P
1
c
1
)
⋯
(
P
m
0
+
P
m
1
+
⋯
+
P
m
c
m
)
(P_1^0+P_1^1+cdots+P_1^{c_1})cdots(P_m^0+P_m^1+cdots+P_m^{c_m})
(P10+P11+⋯+P1c1)⋯(Pm0+Pm1+⋯+Pmcm).
直接用乘法分配律展开，展开完之后一共有 约数个数 项，在每个括号中选取一项相乘，得到的就是一个约数.
AcWing 870. 约数个数
原题链接
给定
n
n
n 个正整数
a
i
a_i
ai，请你输出这些数的乘积的约数个数，答案对
1
0
9
+
7
10^9+7
109+7 取模。
输入格式
第一行包含整数
n
n
n。
接下来
n
n
n 行，每行包含一个整数
a
i
a_i
ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对
1
0
9
+
7
10^9+7
109+7 取模。
数据范围
1
≤
n
≤
100
1≤n≤100
1≤n≤100,
1
≤
a
i
≤
2
×
1
0
9
1≤a_i≤2×10^9
1≤ai≤2×109
输入样例：
3
2
6
8
输出样例：
12
时/空限制： 1s / 64MB
来源： 模板题
算法标签：数学知识 约数 试除法 因式分解
yxc’s Solution
求每个数的乘积的质因数分解的结果
a
1
×
a
2
×
⋯
×
a
n
=
P
1
c
1
P
2
c
2
⋯
P
m
c
m
a_1 times a_2 times cdots times a_n=P_1^{c_1}P_2^{c_2}cdots P_m^{c_m}
a1×a2×⋯×an=P1c1P2c2⋯Pmcm.
可以先将每个数单独分解质因数，将每个结果的指数累加即可.
可以用 map 存储某个质因子的指数是多少.
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int main(){
int n;
scanf("%d",&n);
unordered_mapprimes;
while(n--){
int a;
scanf("%d",&a);
for(int i=2;i<=a/i;++i)
while(a%i==0){
a/=i;
primes[i]++;
}
if(a>1) primes[a]++;
}
LL res=1;
for(auto prime:primes) res=res*(prime.second+1)%mod;
printf("%lld",res);
return 0;
}
AcWing 871. 约数之和
原题链接
给定
n
n
n 个正整数
a
i
a_i
ai，请你输出这些数的乘积的约数之和，答案对
1
0
9
+
7
10^9+7
109+7 取模。
输入格式
第一行包含整数
n
n
n。
接下来
n
n
n 行，每行包含一个整数
a
i
a_i
ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数之和，答案需对
1
0
9
+
7
10^9+7
109+7 取模。
数据范围
1
≤
n
≤
100
1≤n≤100
1≤n≤100,
1
≤
a
i
≤
2
×
1
0
9
1≤a_i≤2×10^9
1≤ai≤2×109
输入样例：
3
2
6
8
输出样例：
252
时/空限制： 1s / 64MB
来源： 模板题
算法标签：数学知识 约数 试除法 因式分解
yxc’s Solution
在处理出来每个质因子和其指数后，需要计算
P
0
+
P
1
+
⋯
+
P
c
P^0+P^1+cdots+P^c
P0+P1+⋯+Pc/则令
t
=
P
×
t
+
1
t=Ptimes t+1
t=P×t+1/
第一次
t
=
P
1
+
1
t=P^1+1
t=P1+1；
第二次
t
=
P
2
+
P
1
+
1
t=P^2+P^1+1
t=P2+P1+1；
第三次
t
=
P
3
+
P
2
+
P
1
+
1
t=P^3+P^2+P^1+1
t=P3+P2+P1+1；
故只需要乘
c
c
c 次即可得到
P
0
+
P
1
+
⋯
+
P
c
P^0+P^1+cdots+P^c
P0+P1+⋯+Pc.
Q：求和不用快速幂吗？
A：其实是不需要的，因为快速幂的时间复杂度为
O
(
log
k
)
O(log k)
O(logk)，其中
k
k
k 为指数；假如一共有
n
n
n 项，每项的指数为
n
n
n，则总的时间复杂度为
O
(
n
log
n
)
O(n log n)
O(nlogn)；但如果使用上述的方法，只需要求
n
n
n 次即可，时间复杂度为
O
(
n
)
O(n)
O(n)，比快速幂更快；
不过
P
0
+
P
1
+
⋯
+
P
c
P^0+P^1+cdots+P^c
P0+P1+⋯+Pc 是有 时间复杂度为
O
(
log
c
)
O(log c)
O(logc) 的时间复杂度的做法的，基本思想是分治.
某一步的要求不高时，没有必要使用一些复杂的算法，即没有必要优化不是算法瓶颈的部分.
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int main(){
int n;
scanf("%d",&n);
unordered_mapprimes;
while(n--){
int a;
scanf("%d",&a);
for(int i=2;i<=a/i;++i)
while(a%i==0){
a/=i;
primes[i]++;
}
if(a>1) primes[a]++;
}
LL res=1;
for(auto prime:primes){
int p=prime.first,c=prime.second;
LL tmp=1;
while(c--) tmp=(tmp*p+1)%mod;
res=res*tmp%mod;
}
printf("%lld",res);
return 0;
}
3.最大公约数——欧几里得算法（辗转相除法）
性质：
d
∣
a
,
d
∣
b
⇒
d
∣
a
+
b
⇒
d
∣
a
x
+
b
y
d|a,d|b Rightarrow d|a+b Rightarrow d|ax+by
d∣a,d∣b⇒d∣a+b⇒d∣ax+by.
即若
d
d
d 能整除
a
a
a，
d
d
d 又能整除
b
b
b，则
d
d
d 能整除
a
+
b
a+b
a+b，进一步
d
d
d 能整除
a
a
a 的倍数
+
+
+
b
b
b 的倍数.
定理：
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
m
o
d
b
)
gcd(a,b)=gcd(b,a mod b)
gcd(a,b)=gcd(b,amodb).
g
c
d
(
a
,
b
)
gcd(a,b)
gcd(a,b) 表示的即为
a
a
a 和
b
b
b 的最大公约数，即最大的
d
=
g
c
d
(
a
,
b
)
d=gcd(a,b)
d=gcd(a,b) 使得
d
∣
a
,
d
∣
b
d|a,d|b
d∣a,d∣b 同时成立；
a
m
o
d
b
=
a
−
⌊
a
b
⌋
×
b
=
a
−
c
×
b
a mod b=a-lfloor frac{a}{b} rfloor times b=a-c times b
amodb=a−⌊ba⌋×b=a−c×b 其中
c
=
⌊
a
b
⌋
c=lfloor frac{a}{b} rfloor
c=⌊ba⌋；
那么原定理就可以写成
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
−
c
×
b
)
gcd(a,b)=gcd(b,a-ctimes b)
gcd(a,b)=gcd(b,a−c×b)；
对于
a
,
b
a,b
a,b 的公约数
d
d
d 来说，其既能整除
a
a
a ，又能整除
b
b
b，则它就一定能整除
a
−
c
×
b
a-ctimes b
a−c×b（
−
c
-c
−c 也算
b
b
b 的倍数）；
同样地，对于
b
,
a
−
c
×
b
b,a-ctimes b
b,a−c×b 的公约数
d
d
d 来说，其既能整除
b
b
b，又能整除
a
−
c
×
b
a-ctimes b
a−c×b，则它一定能整除
a
−
c
×
b
+
c
×
b
=
a
a-ctimes b + ctimes b=a
a−c×b+c×b=a；
故 左式的任何一个公约数 都是 右式的任何一个公约数，反之也成立.
收束条件为：
g
c
d
(
a
,
0
)
=
a
gcd(a,0)=a
gcd(a,0)=a.
AcWing 872. 最大公约数
原题链接
给定
n
n
n 对正整数
a
i
,
b
i
a_i,b_i
ai,bi，请你求出每对数的最大公约数。
输入格式
第一行包含整数
n
n
n。
接下来
n
n
n 行，每行包含一个整数对
a
i
,
b
i
a_i,b_i
ai,bi。
输出格式
输出共
n
n
n 行，每行输出一个整数对的最大公约数。
数据范围
1
≤
n
≤
1
0
5
1≤n≤10^5
1≤n≤105,
1
≤
a
i
,
b
i
≤
2
×
1
0
9
1≤a_i,b_i≤2×10^9
1≤ai,bi≤2×109
输入样例：
2
3 6
4 6
输出样例：
3
2
时/空限制： 1.5s / 64MB
来源： 模板题
算法标签：数学知识 约数 最大公约数 欧几里得算法
yxc’s Solution
#include
#include
using namespace std;
int gcd(int a,int b){
return b ? gcd(b,a%b) : a;
}
int main(){
int n;
scanf("%d",&n);
while(n--){
int a,b;
scanf("%d %d",&a,&b);
printf("%dn",gcd(a,b));
}
return 0;
}
欧几里得算法的时间复杂度为
O
(
l
o
g
(
min
{
a
,
b
}
)
O(log(min{a,b})
O(log(min{a,b}).
证明
不失一般性，不妨设
a
>
b
a>b
a>b，则可以发现，若
b
≠
0
bnot =0
b=0，则会调用
g
c
d
(
b
,
a
%
b
)
gcd(b,a%b)
gcd(b,a%b)；
当然，若
a
<
b
a证毕
本文档基于 AcWing算法基础课 制作
视频链接：第四章 数学知识（一） - AcWing
文档版本：
var1.0 完成于2022.01.31.
