辗转相除法
算法使用
- 要计算\(a\)与\(b\)的最大公约数,且\(a \ ÷ \ b = q \cdots r \ \ \ (a >= b)\).
- 若\(r \not = 0\),可将计算\(a\)与\(b\)的最大公约数,转为计算\(b\)与\(r\)的最大公约数.
- 若\(r = 0\),则\(a\)与\(b\)的最大公约数为\(b\)
数学原理
\[\begin{aligned} 要证 & \textcolor{blue}{gcd(a,b) = gcd(b,r)} \\ & gcd(x,y)表示x和y的最大公约数 \\ 假设&a \ ÷ \ b = q \cdots r , \ a、b、q、r 均为整数 \\ & gcd(a,b) = d_1 , gcd(b,r) = d_2 \\ & a = d_1 \cdot m \ , \ b = d_1 \cdot n , m与n互质 \\ & b = d_2 \cdot i \ , \ r = d_2 \cdot j , i与j互质 \\ \therefore \ & a = b \cdot q + r \\ & r = a - b \cdot q \\ \because \ & r = a - b \cdot q \\ & \ \ = d_1 \cdot m - d_1 \cdot n \cdot q \\ & \ \ = d_1 (m - n \cdot q) \\ \therefore \ & r \ ÷ \ d_1 = m - n \cdot q 为整数 \\ & d_1 是 r 的约数 \\ \therefore \ & \textcolor{orange}{d_1是a、b、r的公约数} \\ \therefore \ & \textcolor{orange}{d_1 <= d_2} \\ \because \ & a = b \cdot q + r \\ & \ \ = d_2 \cdot i \cdot q + d_2 \cdot j \\ & \ \ = d_2(i \cdot q + j) \\ \therefore \ & a \ ÷ \ d_2 = i \cdot q + j 为整数 \\ & d_2 是 a 的约数 \\ \therefore \ & \textcolor{orange}{d_2是a、b、r的公约数} \\ \therefore \ & \textcolor{orange}{d_2 <= d_1} \\ \therefore \ & \textcolor{blue}{d_1 = d_2} \\ & \textcolor{blue}{gcd(a,b) = gcd(b,r)} \end{aligned} \]代码实现
int gcd(int a , int b)
{
if(a < b) swap(a,b);
return b > 0 ? gcd(b,a % b) : a;
}
更相减损术
算法使用
- 要计算\(a\)与\(b\)的最大公约数,且\(a >= b\).
- 若\(a - b \not = b\),可将计算\(a\)与\(b\)的最大公约数,转为计算\(a - b\)与\(b\)的最大公约数.
- 若\(a - b = b\),则\(a\)与\(b\)的最大公约数为\(b\)
数学原理
\[\begin{aligned} 要证 & \textcolor{blue}{gcd(a,b) = gcd(b,a - b)} , a > b \\ & gcd(x,y)表示x和y的最大公约数 \\ 假设 & gcd(a,b) = d_1 , gcd(b,a - b) = d_2 \\ & a = d_1 \cdot m \ , \ b = d_1 \cdot n , m与n互质 \\ & a - b = d_2 \cdot i \ , \ b = d_2 \cdot j , i与j互质 \\ \because \ & a - b = d_1(m - n) \\ \therefore \ & \begin{cases} \textcolor{red}{a = d_1 \cdot m} \\ \textcolor{red}{b = d_1 \cdot n} \\ \textcolor{red}{a - b = d_1 \cdot (m - n)} \\ \end{cases} \\ \therefore \ & \textcolor{orange}{d_1是a、b、a-b的公约数} \\ & \textcolor{orange}{d_1 <= d_2} \\ \because \ & a = d_2 (i + j) \\ \therefore \ & \begin{cases} \textcolor{red}{a = d_2 \cdot (i + j)} \\ \textcolor{red}{b = d_2 \cdot j} \\ \textcolor{red}{a - b = d_2 \cdot i} \\ \end{cases} \\ \therefore \ & \textcolor{orange}{d_2是a、b、a-b的公约数} \\ & \textcolor{orange}{d_2 <= d_1} \\ \therefore \ & \textcolor{blue}{d_1 = d_2} \\ & \textcolor{blue}{gcd(a,b) = gcd(b,a - b)} \\ \end{aligned} \]代码实现
int gcd(int a , int b)
{
if(a == b) return a;
return gcd(max(a,b) - min(a,b),min(a,b));
}
更相减损术优化
算法使用
- 要计算\(a\)与\(b\)的最大公约数,且\((a >= b)\).
- 若\(a \not = b\),
- 若 \(a \ \% \ 2 = 0\) 且 \(b \ \% \ 2 = 0\),则可将计算 \(a\) 与 \(b\) 的最大公约数,转为计算 \(a \ \% \ 2\) 与 \(b \ \ \% \ 2\) 的最大公约数乘上\(2\).
- 若 \(a \ \% \ 2 = 0\) 且 \(b \ \% \ 2 \not = 0\),则可将计算 \(a\) 与 \(b\) 的最大公约数,转为计算 \(a \ \% \ 2\) 与 \(b\) 的最大公约数.
- 若 \(a \ \% \ 2 \not = 0\) 且 \(b \ \% \ 2 = 0\),则可将计算 \(a\) 与 \(b\) 的最大公约数,转为计算 \(a\) 与 \(b \ \ \% \ 2\) 的最大公约数.
- 若 \(a \ \% \ 2 \not = 0\) 且 \(b \ \% \ 2 \not = 0\),则可将计算 \(a\) 与 \(b\) 的最大公约数,转为计算 \(a - b\) 与 \(b\) 的最大公约数.
- 若\(a = b\),则 \(a\) 与 \(b\) 的最大公约数为\(b\)
- 若\(a \not = b\),
数学原理
更相减损术在两个整数相差较大时,递归多次影响性能,在此时可以通过简单位运算改善性能
代码实现
int gcd(int a , int b)
{
if(a == b) return b;
if(!(a & 1) && !(b & 1)) return gcd(a >> 1,b >> 1) << 1;
if(!(a & 1) && b & 1) return gcd(a >> 1,b);
if(a & 1 && !(b & 1)) return gcd(a,b >> 1);
return gcd(max(a,b) - min(a,b),min(a,b));
}