二进制方法中,只需要移位(<<和>>)和加减操作(+和-),不像欧几里德算法中需要乘法和除法运算。虽然算法效率更高,但是程序的可读性和可维护性差一些。
如果设d=gcd(u,v) = u.x + v.y, 本算法涉及到六种操作:
1)已知ext_gcd(u,v)如何求ext_gcd(u,2v)=u'.x' + v'.y',其中u为奇数,v可奇可偶,d=gcd(u,v)为奇数;
2)已知ext_gcd(u,v)如何求ext_gcd(2u,v)=u'.x' + v'.y',其中v为奇数,u可奇可偶,d=gcd(u,v)为奇数;
3)已知ext_gcd(u-v,v)如何求ext_gcd(u,v)=u'.x' + v'.y';
4)已知ext_gcd(u,u-v)如何求ext_......
阅读全文