辗转相除法和辗转相减法

除法和辗转相减法"/>

辗转相除法和辗转相减法

辗转相除法和辗转相减法

欧几里得算法（辗转相除法）

基本公式

gcd ⁡ ( a , b ) = gcd ⁡ ( b , a m o d b ) \gcd (a,b) = \gcd (b,a\mod b) gcd(a,b)=gcd(b,amodb)

终止条件是 b = 0 b = 0 b=0，此时答案为 a a a。

实现方法

时间复杂度近似为 O ( max ⁡ ( a , b ) ) \mathcal{O}(\max(a,b)) O(max(a,b))

递归版本：

int gcd(int a, int b) {if (b == 0)return a;return gcd(b, a % b);
}

非递归版本（推荐）：

int gcd(int a, int b) {while(b) {a %= b;// 交换 a 跟 b 的值b ^= a;a ^= b;b ^= a;}return a;
}

更相减损术（辗转相减法）

注意：本算法的时间复杂度较高，在 a , b a,b a,b的差的绝对值较大的时候会很慢，但他为加减法计算最大公约数提供了一种方式。

基本公式

gcd ⁡ ( a , b ) = gcd ⁡ ( max ⁡ ( a , b ) − min ⁡ ( a , b ) , min ⁡ ( a , b ) ) \gcd (a,b) = \gcd(\max(a,b) - \min(a,b),\min(a,b)) gcd(a,b)=gcd(max(a,b)−min(a,b),min(a,b))

终止条件是 a = b a = b a=b，答案为 gcd ⁡ ( a , b ) = gcd ⁡ ( a , a ) = a \gcd (a,b) = \gcd(a,a) = a gcd(a,b)=gcd(a,a)=a。

显然优化

注意到：

容易证明：当 a , b a,b a,b均为偶数的时候，可同时对 a , b a,b a,b除以 2 2 2，并对最终答案乘以 2 2 2。

类似的，易知 a , b a,b a,b中有且仅有一个偶数的时候，可以对这个偶数除以 2 2 2，但不影响最终答案。

这样，复杂度就基本稳定在了 O ( log ⁡ max ⁡ ( a , b ) ) \mathcal{O}(\log \max (a,b)) O(logmax(a,b))。

实现方法

int gcd(int x,int y){int ans = 1;while(x != y){if(x % 2 == 0 && y % 2 == 0) ans <<= 1;else if(x % 2 == 0) x >>= 1;else if(y % 2 == 0) y >>= 1;if(x > y) x -= y;else if(x < y) y -= x;}return ans * x;
}