这一小节主要讲解的是数论，主要包括了质数，约数，欧几里得算法。
对所有的大于1的自然数字，定义了【质数/合数】这一概念。对于所有小于等于1的自然数，没有这个概念，它们既不是质数也不是合数。
质数的定义：对于大于1的自然数，如果这个数的约数只包含1和它本身，则这个数被称为质数，或者素数
采用试除法。
对于一个数n，从2枚举到n-1，若有数能够整除n，则说明除了1和n本身，n还有其他约数，则n不是质数；否则，n是质数
优化：由于一个数的约数都是成对出现的。比如12的一组约数是3，4，另一组约数是2，6。则我们只需要枚举较小的那一个约数即可
我们用 d ∣ n d | n d∣n来表示d整除n，比如 3 ∣ 12 3|12 3∣12
只要满足 d ∣ n d|n d∣n，则一定有 n d ∣ n \frac{n}{d} | n dn∣n，因为约数总是成对出现的
比如 3 ∣ 12 3|12 3∣12，就一定有 4 ∣ 12 4|12 4∣12
我们只枚举小的那一部分的数即可，令 d ≤ n d d \le \frac{n}{d} d≤dn，则 d ≤ n d \le \sqrt{n} d≤n
则对于数n，只需要枚举2到 n \sqrt{n} n 即可
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;
}
注意有一个细节，for循环的结束条件，推荐写成i <= n / i。
有的人可能会写成 i <= sqrt(n)，这样每次循环都会执行一次sqrt函数，而这个函数是有一定时间复杂度的。而有的人可能会写成
i * i < =n，这样当i很大的时候（比如i比较接近int的最大值时），i * i可能会溢出，从而导致结果错误。
#include<iostream>
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 m;
scanf("%d", &m);
while(m--) {
int a;
scanf("%d", &a);
if(is_prime(a)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
还是采用试除法。
对于一个数N，总能够写成如下的式子：
N = P 1 k 1 × P 2 k 2 × . . . . . . P n k n N = P_1^{k_1} × P_2^{k_2} × ......P_n^{k_n} N=P1k1×P2k2×......Pnkn，其中 P 1 P_1 P1到 P n P_n Pn皆是质数， k 1 k_1 k1 到 k n k_n kn 都是大于0的正整数。
对于一个数 n n n 求解质因数的过程如下：
从2到n，枚举所有数，依次判断是否能够整除 n 即可。
这里可能有个疑问，不是应当枚举所有的质数吗？怎么是枚举所有数？枚举所有数如果取到合数怎么办？那分解出来的就不是质因子了啊。
下面进行一下解释：
我们枚举数时，对于每个能整除n的数，先把这个数除干净了，再继续枚举后面的数，这样能保证，后续再遇到能整除的数，一定是质数而不是合数。
除干净是什么意思呢？比如 n=24，我们先枚举2，发现2能整除24，则除之，24÷2=12，得到的结果是12，发现2仍然能整除之，则除之，12÷2=6，仍能整除，除之！6÷2=3。2不能整除3了。则停止。继续枚举下一个数3，3÷3=1。
质因数分解结束。则 24 = 2 3 × 3 1 24=2^3×3^1 24=23×31，24的质因子就有两个，分别是2和3。
那么，把一个数除干净了，怎么就能保证后续遇到能整除的数一定是质数了呢？
假设后续枚举到一个合数k，这个合数能整除n，则这个合数的某个质因子p，也能整除n。就比如合数6能整除24，则6的质因子2，肯定也能整除24。
合数k的质因子p一定比合数本身小，而我们是从小到大进行枚举，则p一定在k之前被枚举过了，而之前枚举p时，是把p除干净了的，此时不应当还能被p整除，这就矛盾了。所以在枚举时，如果遇到能整除的数，只可能是质数，而不可能是合数。（我们是从2开始枚举的，而2是一个质数）
void divide(int n) {
for(int i = 2; i <= n; i++) {
if(n % i == 0) {
int s = 0;
while(n % i == 0) {
s++;
n /= i;
}
printf("%d %d\n", i, s);
}
}
}
从2枚举到n，时间复杂度就是O(n)。其实不必枚举到n。下面进行一下优化
有一个重要性质： n n n 中最多只包含一个大于 n \sqrt{n} n 的质因子
这个结论很好证明，因为我们知道一个数 n n n 分解质因数后可以写成
n = P 1 k 1 × P 2 k 2 × . . . . . . P n k n n = P_1^{k_1} × P_2^{k_2} × ......P_n^{k_n} n=P1k1×P2k2×......Pnkn
其中 P 1 P_1 P1 到 P n P_n Pn 都是 n n n 的质因子，若存在两个大于 n \sqrt{n} n 的质因子，就算两个质因子的指数都是最小的1，这两个质因子乘起来也大于 n n n 了，于是就矛盾了。
所以我们只用枚举到 n \sqrt{n} n 即可，即枚举的 i i i 一定满足 i ≤ n i \le \sqrt{n} i≤n ，即 i ≤ n i i \le \frac{n}{i} i≤in
优化后的求解质因子的代码如下（时间复杂度为 O ( n ) O(\sqrt{n}) O(n )）
void divide(int n) {
for(int i = 2; i <= n / i; i++) {
if(n % i == 0) {
int s = 0;
while(n % i == 0) {
s++;
n /= i;
}
printf("%d %d\n", i, s);
}
}
// 如果除完之后, n是大于1的,
// 说明此时的n就是那个大于 原根号n 的最大的质因子, 单独输出一下
if(n > 1) printf("%d %d\n", n, 1);
}
注意枚举完毕后，如果最终的n不等于1，则最后剩下的这个n，就是最大的一个质因子（大于原来的 n \sqrt{n} n 的那个质因子），需要单独输出一下。
比如 n=39，由于枚举时的条件是 i ≤ n i i \le \frac{n}{i} i≤in ，则只会枚举到6，for循环就结束了，而39有一个质因子是13
复习的时候发现，上面的说法有误！需要特别注意！上面for循环中的i <= n ，或者i <= n / i，需要注意n本身是逐渐变小的。比如对于39，在枚举到i = 3时，n已经减小为13了，在下一轮循环时，i = 4，而此时判断n / i = 13 / 4 = 3，而3 < 4，所以i <= n / i条件已经不满足，所以实际循环只枚举了i = 3，在i = 4时，就因为不满足循环条件，而结束循环了。不会像上面说的，39会枚举到6。需要特别注意！！由于每轮循环都会从n中将一个质数除干净，所以n是不断变小的，而for循环的条件，i <= n / i 也是动态变化的。虽然这不影响算法的正确性，但是不能对算法带有错误的理解。
#include<iostream>
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) {
s++;
n /= i;
}
printf("%d %d\n", i, s);
}
}
if(n > 1) printf("%d %d\n", n, 1);
}
int main() {
int m;
scanf("%d", &m);
while(m--) {
int a;
scanf("%d", &a);
divide(a);
printf("\n");
}
return 0;
}
对于一个数n，求解1~n中质数的个数
将2到n全部数放在一个集合中，遍历2到n，删除集合中这个数的倍数。最后集合中剩下的数就是质数。
解释：如果一个数p没有被删掉，那么说明在2到p-1之间的所有数，p都不是其倍数，即2到p-1之间，不存在p的约数。故p一定是质数。
时间复杂度：
n 2 + n 3 + . . . . + n n = n ( 1 2 + 1 3 + . . . . + 1 n ) = n ln n \frac{n}{2}+\frac{n}{3}+....+\frac{n}{n} = n(\frac{1}{2} + \frac{1}{3} + ....+\frac{1}{n})=n\ln n 2n+3n+....+nn=n(21+31+....+n1)=nlnn
而 n ln n = n log e n n\ln n = n\log_en nlnn=nlogen，而 e = 2.71828 e=2.71828 e=2.71828左右，是大于2的，所以 n ln n < n l o g 2 n n\ln n \lt nlog_2n nlnn<nlog2n
故，朴素思路筛选质数的时间复杂度大约为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int ctn;
bool st[N];
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) ctn++; // i是质数
for(int j = i; j <= n; j += i) st[j] = true; // 删数
}
}
int main() {
int n;
scanf("%d", &n);
get_primes(n);
printf("%d", ctn);
}
其实上面的代码的运行过程不是完全按照朴素思路所描述的那样。上面的代码用一个布尔数组来表示一个数是否被删除。
遍历2到n，对每个数，先看一下其是否被删除了，若没有，则说明其是一个质数，随后将这个数以及其倍数全部删除（布尔数组置为true）。每当遍历到一个数时，如果这个数没有被前面的数所删掉，则说明这个数是个质数。
其实不需要把全部数的倍数删掉，而只需要删除质数的倍数即可。
对于一个数p，判断其是否是质数，其实不需要把2到p-1全部数的倍数删一遍，只要删掉2到p-1之间的质数的倍数即可。因为，若p不是个质数，则其在2到p-1之间，一定有质因数，只需要删除其质因数的倍数，则p就能够被删掉。优化后的代码如下
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int ctn;
bool st[N];
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) {
ctn++;
for(int j = i; j <= n; j += i) st[j] = true;
}
}
}
int main() {
int n;
scanf("%d", &n);
get_primes(n);
printf("%d", ctn);
}
那么优化后的时间复杂度如何呢？
原本我们需要对每个数都删掉其倍数，现在只需要对是质数的数，删掉其倍数。需要操作的数的个数明显减少了很多。要估算优化后的算法的时间复杂度，问题是，质数的个数究竟有多少个呢？
根据质数定理，在1到n之间，质数的个数大约为 n ln n \frac{n}{\ln n} lnnn，我们原本需要对n个数进行操作，现在只需要对 n ln n \frac{n}{\ln n} lnnn个数进行操作，所以时间复杂度就除以个 ln n \ln n lnn（其实这样算是不正确的），即 n ln n ÷ ln n = n n\ln n \div \ln n = n nlnn÷lnn=n，所以优化后的算法的时间复杂度大约是 O ( n ) O(n) O(n)，其实准确复杂度是 n log log n n\log{\log n} nloglogn。
这种优化后的筛选质数的方法，被称为埃氏筛法（埃拉托斯特尼筛法）。
下面多介绍一种线性筛法，其性能要优于埃氏筛法（在106 下两个算法差不多，在107下线性筛法大概快一倍），其思想也类似，把每个合数，用它的某一个质因子删掉就可以了。
核心思路是：对于某一个合数n，其只会被自己的最小质因子给筛掉。
先上一下代码
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int ctn;
int primes[N];
bool st[N];
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) primes[ctn++] = i;
for(int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
// 当下面的if条件成立时, primes[j]一定是i的最小质因子
if(i % primes[j] == 0) break;
}
}
}
int main() {
int n;
scanf("%d", &n);
get_primes(n);
printf("%d", ctn);
}
对上面的代码解释如下：
用
p
j
pj
pj 来表示primes[j]
当 i % p j = 0 i \% pj = 0 i%pj=0时
p j pj pj一定是 i i i 的最小质因子，因为我们是从小到大枚举质数的，首先遇到的满足 i % p j = 0 i \% pj = 0 i%pj=0的， p j pj pj一定是 i i i 的最小质因子，
并且 p j pj pj 一定是 p j × i pj \times i pj×i 的最小质因子。
这么说可能不太好理解，假设4的最小质因子为2，写成分解质因数的形式，即为 4 = 2 2 4=2^2 4=22。
则，4的倍数中最小的数，且最小质因子同样是2的，一定是给4本身，再乘以一个其最小质因子，得到的数，即8。
再举个例子， 15 = 3 × 5 15 = 3 \times 5 15=3×5，15的最小质因子是3，则15的倍数中最小的数，且最小质因子同样是3的，一定是给15乘以一个最小质因子3，即45。
当 i % p j ≠ 0 i \% pj \ne 0 i%pj=0 时
p j pj pj 一定不是 i i i 的质因子。并且由于是从小到大枚举质数的，那么 p j pj pj 一定小于 i i i 的全部质因子。那么 p j pj pj 就一定是 p j × i pj \times i pj×i 的最小质因子。
则无论哪种情况， p j pj pj 都一定是 p j × i pj \times i pj×i 的最小质因子。
那么线性筛法是如何保证，所有的合数都一定能被删掉呢？ 假设，有一个合数 x x x，那么其一定有一个最小质因子 p j pj pj，那么当枚举到 i = x p j i = \frac{x}{pj} i=pjx 的时候，就能把 x x x 删掉
线性筛法保证了，每个合数，都是被其最小质因子给删掉的，且只会被删一次
运行时间如下
从上往下依次是线性筛法，埃氏筛法，朴素筛法。
三种筛选质数的方法，都是基于删除数来完成的，我们只要删除合数，剩下的就是质数了。由于质数的约数只有1和它本身，而合数一定存在其他约数。先想一个比较朴素的暴力做法，那么就是枚举2到n，依次删除每个数的倍数，那么n以内的全部合数就被删除完毕，剩下的数就是质数。
用动图表示如下（动图来源于知乎，原链接在此）
朴素筛法代码如下
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) ctn++; // i是质数
for(int j = i; j <= n; j += i) st[j] = true; // 删数
}
}
随后，反观这个过程，我们考虑如何进行优化。
首先，暴力做法枚举了2到n全部的数，它做的无用功主要有
枚举的过程中，有些后面的数已经被前面的数的倍数给删掉了，但也会枚举到
比如4，在枚举2的时候已经被删除了，但还是会被枚举到
删除时，有的数已经被前面的数删了，但还可能会被后面的数再删一次
比如6，在枚举2时已经被删除了，但在枚举3时还会被再删一次
针对1，没什么好优化的，因为在算法执行过程中，被删除的数是动态变化的，我们并不能预先确定哪些数不需要枚举。
优化主要针对2。我们的目的是删除合数，做法是通过删除一个数的倍数来完成。因为每个合数都能够分解质因数，合数一定是某个质数的倍数。所以，我们其实不需要删除所有数的倍数，只需要删除所有质数的倍数，即可删除所有合数。
故可对朴素筛法进行优化，仅当枚举到的是质数时，才执行删除。这便是埃氏筛法，代码如下
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) {
ctn++; // i 是质数
for(int j = i; j <= n; j += i) st[j] = true; // 删除这个质数的倍数
}
}
}
埃氏筛法能优化算法性能，但还不是最优。我们考虑6这个合数，它会被质数2删除一次，还会被质数3再删除一次。
于是，我们接着想，删除一个合数，其实只需要删除这个合数的最小质因子的倍数即可。比如6有两个质因子，2和3，其实只需要用2来删除即可。这便是线性筛法。线性筛法需要记录质数，故需要开一个额外的数组来存质数。其代码如下
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) primes[ctn++] = i; // i 是质数
for(int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
线性筛法的思想很简单：对每个合数，都用其最小质因子的倍数来删掉它。但是代码理解起来不是很容易。下面进行一个说明
首先从2到n，枚举每个数，用 i i i 表示当前枚举的数，边枚举边保存得到的质数，则 p r i m e s primes primes 数组中保存的是小于等于 i i i 的全部质数。
在每次枚举 i i i 时，尝试枚举小于 i i i 的全部质数，即尝试枚举全部的 p r i m e s primes primes 数组，并尝试删除 p r i m e s j × i primes_j \times i primesj×i
需要保证 p r i m e s j × i primes_j \times i primesj×i 小于等于 n n n ，因为我们求的是 n n n 以内的质数，删除合数只需要删除小于 n n n 的合数即可，否则会导致 s t st st 数组越界。
每次从最小的质数开始枚举，删除 p r i m e s j × i primes_j \times i primesj×i。因为，无论 p r i m e s j primes_j primesj 能否整除 i i i，都能保证 p r i m e s j primes_j primesj 一定是 p r i m e s j × i primes_j \times i primesj×i 的最小质因子。
而当 i % p r i m e s j = 0 i \% primes_j = 0 i%primesj=0 时，退出循环。
为什么在 i % p r i m e s j = 0 i \% primes_j = 0 i%primesj=0 时要退出呢？这是为了保证，每个合数都被其最小质因子给删掉，且只删一次。
假设在
i
%
p
r
i
m
e
s
j
=
0
i \% primes_j = 0
i%primesj=0 时不退出循环，则下一轮会枚举到下一个质数
p
r
i
m
e
s
j
+
1
primes_{j+1}
primesj+1 ，此时会删除
p
r
i
m
e
s
j
+
1
×
i
primes_{j+1} \times i
primesj+1×i ，且是用的
p
r
i
m
e
s
j
+
1
primes_{j+1}
primesj+1 去删除的，但
p
r
i
m
e
s
j
+
1
×
i
primes_{j+1} \times i
primesj+1×i 的最小质因子应该是
p
r
i
m
e
s
j
primes_j
primesj，因为
i
%
p
r
i
m
e
s
j
=
0
i \% primes_j = 0
i%primesj=0 。而对于每个合数，我们应当用其最小质因子来删掉它。所以这里需要break。
并且，如果不break的话，下一轮j++可能导致
p
r
i
m
e
s
primes
primes 数组越界。
其实，在
i
%
p
r
i
m
e
s
j
=
0
i \% primes_j = 0
i%primesj=0 时也可以不break，但是为了防止j越界，此时应当在循环条件中加上
j
<
c
t
n
j \lt ctn
j<ctn ，这样才能保证算法正确性。但是如此以来，会导致一个合数被删除多次，所以其性能会有所降低，并不能算是线性筛法。
如果在
i
%
p
r
i
m
e
s
j
=
0
i \% primes_j = 0
i%primesj=0 时 break 了，则能保证每个合数都只被删除一次，且都是被其最小质因子删除的。并且也能保证枚举
p
r
i
m
e
s
primes
primes 数组时，
j
j
j 不会越界。因为
p
r
i
m
e
s
primes
primes 数组存储的是小于等于
i
i
i 的所有质数，
若
i
i
i 是合数，则一定存在一个小于
i
i
i 的质数，能够整除
i
i
i，则一定会在
j
j
j 越界前break掉；
若 i i i 是质数，那么 i i i 一定是当前 p r i m e s primes primes 数组中的最后一个数，则在 j j j 的最后一个位置一定会有 p r i m e s j = i primes_j = i primesj=i，所以 j j j 也不会越界。
试除法求一个数的所有约数，和试除法判断质数的思路一样
#include<iostream>
using namespace std;
const int N = 2e8 + 10;
int l[N], h[N];
void get_dividers(int n) {
// 只枚举较小的约数即可
int lctn = 0, hctn = 0;
for(int i = 1; i <= n / i; i++) {
if(n % i == 0) {
l[lctn++] = i;
if(i != n / i) h[hctn++] = n / i; // 重复约数需要排除
}
}
for(int i = 0; i < lctn; i++) printf("%d ", l[i]);
for(int i = hctn - 1; i >= 0; i--) printf("%d ", h[i]);
printf("\n");
}
int main() {
int m;
scanf("%d", &m);
while(m--) {
int n;
scanf("%d", &n);
get_dividers(n);
}
return 0;
}
假设一个数 N N N ，其分解质因数可写成 N = P 1 k 1 × P 2 k 2 × . . . . . . P n k n N = P_1^{k_1} × P_2^{k_2} × ......P_n^{k_n} N=P1k1×P2k2×......Pnkn
则 N N N 的约数个数为 ( k 1 + 1 ) × ( k 2 + 1 ) × . . . . × ( k n + 1 ) (k_1+1) \times (k_2+1) \times .... \times (k_n+1) (k1+1)×(k2+1)×....×(kn+1)
其实就是排列组合。
对于 N N N 的每个质因子，我们在构造一个约数时，可以选择是否将其纳入。
比如对于质因子 P 1 P_1 P1，它的指数是 k 1 k_1 k1，则我们有 k 1 + 1 k_1+1 k1+1 种选择，即：纳入 0 0 0 个 P 1 P_1 P1，纳入 1 1 1 个 P 1 P_1 P1，…，纳入 k 1 k_1 k1 个 P 1 P_1 P1，对于质因子 P 2 P_2 P2 同理。
当所有的质因子我们都不纳入时，得到的约数就是 1 1 1，当所有的质因子我们全纳入时（每个质因子的指数取最大），得到的约数就是 N N N 本身。
一共有多少种组合方式呢？
对于每个质因子 P i P_i Pi 我们都有 k i + 1 k_i + 1 ki+1 种选择，总共的组合方式就是将每个质因子的选择数相乘，即得到上面的公式。
在int范围内的全部数，约数个数最多的一个数，其约数个数大概有1500个
#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 1e9 + 7;
int main() {
int m;
scanf("%d", &m);
unordered_map<int, int> primes; // 计数所有的质因子及其指数
while(m--) {
int n;
scanf("%d", &n);
for(int i = 2; i <= n / i; i++) {
while(n % i == 0) {
n /= i;
primes[i]++;
}
}
if(n > 1) primes[n]++;
}
unordered_map<int, int>::iterator it = primes.begin();
LL res = 1;
while(it != primes.end()) {
res = (res * (it->second + 1)) % N;
it++;
}
printf("%lld", res);
return 0;
}
数 N N N 的所有约数之和等于
( P 1 0 + P 1 1 + . . . + P 1 k 1 ) × . . . . . × ( P n 0 + P n 1 + . . . + P n k n ) (P_1^0+P_1^1+...+P_1^{k_1}) \times ..... \times (P_n^0+P_n^1+...+P_n^{k_n}) (P10+P11+...+P1k1)×.....×(Pn0+Pn1+...+Pnkn)
将上面的式子按照乘法分配律展开，会得到如下的形式
( . . × . . ) + ( . . × . . ) + ( . . × . . ) + . . . (.. \times ..) + (.. \times ..) + (.. \times ..) + ... (..×..)+(..×..)+(..×..)+...
每一项都是一个乘积，而这个乘积，就是从每个 P i P_i Pi 中选择了一项，互相乘了起来，这一个乘积就是 N N N 的一个约数。
#include<iostream>
#include<unordered_map>
using namespace std;
const int N = 1e9 + 7;
typedef long long LL;
int main() {
int m;
scanf("%d", &m);
unordered_map<int, int> primes;
while(m--) {
int n;
scanf("%d", &n);
for(int i = 2; i <= n / i; i++) {
while(n % i == 0) {
primes[i]++;
n /= i;
}
}
if(n > 1) primes[n]++;
}
LL res = 1;
for(auto p : primes) {
int a = p.first, b = p.second; // 质因数的底数和指数
LL t = 1;
for(int i = 0; i < b; i++) {
t = (t * a + 1) % N;
}
res = (res * t) % N;
}
printf("%lld", res);
return 0;
}
欧几里得算法（辗转相除法）
我们用 g c d ( a , b ) gcd(a,b) gcd(a,b) 来表示 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 ( 42 , 12 ) gcd(42,12) gcd(42,12)，由于 a m o d b ≠ 0 a \mod b \ne 0 amodb=0，则求解 g c d ( 12 , 42 m o d 12 ) = g c d ( 12 , 6 ) gcd(12, 42 \mod 12) = gcd(12,6) gcd(12,42mod12)=gcd(12,6)，而 g c d ( 12 , 6 ) gcd(12,6) gcd(12,6) 发现 6 6 6 能整除 12 12 12，则最大公约数就是 6 6 6
对上述算法的正确性，证明如下：
假设 a a a 和 b b b 的最大公约数是 k k k ，则 a = k × a k a = k \times a_k a=k×ak， b = k × b k b = k \times b_k b=k×bk，由于 k k k 是最大的公约数，则容易得知 a k a_k ak 和 b k b_k bk 一定是互质的（若不互质的话， a k a_k ak 和 b k b_k bk 一定存在一个大于1的公约数，可以将这个约数乘到 k k k 上，这样就使得 a a a 和 b b b 的最大公约数不是 k k k 了，而是 k k k 的某个倍数）。
由于公式中需要 a m o d b a \mod b amodb，所以我们将 a a a 写成 a = c × b + d a = c \times b + d a=c×b+d，将 c × b + d c \times b + d c×b+d 中的 b b b 用 k × b k k \times b_k k×bk 替换，得到 k × b k × c + d k \times b_k \times c + d k×bk×c+d
即 k × b k × c + d = k × a k k \times b_k \times c + d = k \times a_k k×bk×c+d=k×ak，在等式左半边的部分将 k k k 提取出来
即 k × （ b k × c + d k ） = k × a k k \times （b_k \times c + \frac{d}{k}） = k \times a_k k×（bk×c+kd）=k×ak，消掉 k k k，得 b k × c + d k = a k b_k \times c + \frac{d}{k} = a_k bk×c+kd=ak
由于 a k a_k ak 是个整数，则 b k × c + d k b_k \times c + \frac{d}{k} bk×c+kd 一定是个整数，即 d k \frac{d}{k} kd 一定是整数 ， d d d 一定是 k k k 的倍数，即 d = d k × k d = d_k \times k d=dk×k。
由于 d = a m o d b d = a \mod b d=amodb，于是，我们推导出了， a m o d b a \mod b amodb 一定是 a a a 和 b b b 的最大公约数 k k k 的倍数。由于我们的公式是 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)，那还存在一个问题，虽然 d d d 也是 k k k 的倍数，但 b b b 和 d d d 的最大公约数一定就是 k k k 吗？也就是说， g c d ( b , a m o d b ) gcd(b, a \mod b) gcd(b,amodb) 的答案一定等价于 g c d ( a , b ) gcd(a,b) gcd(a,b) 吗？这是一定的。下面采用反证法进行说明。
若 d d d 和 b b b 的最大公约数大于 k k k ，假设为 k p l u s k_{plus} kplus ，则有 b = b k p × k p l u s b = b_{kp} \times k_{plus} b=bkp×kplus， d = d k p × k p l u s d=d_{kp} \times k_{plus} d=dkp×kplus，将这两项带入到 a = c × b + d a = c \times b + d a=c×b+d 当中，有 a = c × b k p × k p l u s + d k p × k p l u s a = c \times b_{kp} \times k_{plus} + d_{kp} \times k_{plus} a=c×bkp×kplus+dkp×kplus，可以将 k p l u s k_{plus} kplus 提取出来，则说明 a a a 有一个大于 k k k 的约数 k p l u s k_{plus} kplus ，而 k p l u s k_{plus} kplus 同时也是 b b b 的约数，则 a a a 和 b b b 存在一个大于 k k k 的约数 k p l u s k_{plus} kplus ，这与 k k k 是 a a a 和 b b b 的最大公约数矛盾了。所以， b b b 和 d d d 的最大公约数一定是 k k k 。
所以求解 k k k，就相当于求解 b b b 和 d d d 的最大公约数，即相当于求 b b b 和 a m o d b a \mod b amodb 的最大公约数。
在编写代码时，一开始会考虑到， 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) ，是否需要注意 a a a 和 b b b 的大小位置关系（是否一定需要保证 a > b a \gt b a>b 呢？），实际发现不用。
举例如下
假设求解 12 12 12 和 30 30 30 的最大公约数，如果我们写成 g c d ( 12 , 30 ) gcd(12, 30) gcd(12,30)
则 g c d ( 12 , 30 ) = g c d ( 30 , 12 m o d 30 ) = g c d ( 30 , 12 ) gcd(12,30) = gcd(30, 12 \mod 30) = gcd(30, 12) gcd(12,30)=gcd(30,12mod30)=gcd(30,12)，会自动调整好顺序，使得 a > b a \gt b a>b ，只是多一层递归而已。
随后便是 g c d ( 30 , 12 ) = g c d ( 12 , 6 ) = 6 gcd(30,12) = gcd(12, 6) = 6 gcd(30,12)=gcd(12,6)=6
#include<iostream>
using namespace std;
// 写代码时可以假设一定满足 a > b
// 就算 a < b , 也会在第一次递归时调转位置
int gcd(int a, int b) {
// b == 0 时, 直接返回a, 否则进行辗转相除
return b ? gcd(b, a % b) : a;
}
int main() {
int m;
scanf("%d", &m);
while(m--) {
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", gcd(a, b));
}
return 0;
}
(已于2021/07/23 更新，更新内容为校正了辗转相除法求最大公约数的推导过程)