除法和辗转相减法"/>
辗转相除法和辗转相减法
辗转相除法和辗转相减法
欧几里得算法(辗转相除法)
基本公式
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;
}
更多推荐
辗转相除法和辗转相减法
发布评论