0001 __int64 gcdCN ( __int64 a, __int64 b ) { //assert: 0 < min(a, b) 0002 int r = 0; //a和b的2^r形式的公因子 0003 while ( ! ( ( a & 1 ) || ( b & 1 ) ) ) { //若a和b都是偶数 0004 a >>= 1; b >>= 1; r ++; //则同时除2(右移),并累加至r 0005 } //以下,a和b至多其一为偶 0006 while ( 1 ) { 0007 while ( ! ( a & 1 ) ) a >>= 1; //若a偶(b奇),则剔除a的所有因子2 0008 while ( ! ( b & 1 ) ) b >>= 1; //若b偶(a奇),则剔除b的所有因子2 0009 ( a > b ) ? a = a - b : b = b - a; //简化为:gcd(max(a, b) - min(a, b), min(a, b)) 0010 if ( 0 == a ) return b << r; //简化至平凡情况:gcd(0, b) = b 0011 if ( 0 == b ) return a << r; //简化至平凡情况:gcd(a, 0) = a 0012 } 0013 }