两个数的异或等于两个数的最大公因数，c++使用逆元的方法实现

在计算机科学中，利用异或(XOR)操作来求解两个数的最大公约数(GCD，Greatest Common Divisor)是一个巧妙的技巧。这是因为对于任意整数a和b，它们的异或结果与它们的最大公约数有以下性质：

如果a % b == 0（即a能被b整除），那么a ^ b的结果就是b；如果a不能被b整除，a ^ b的结果将是两者奇偶性的不同，也就是它们之间的最小非零公倍数。

为了使用这个特性找到两个数的最大公约数，可以采用欧几里得算法（辗转相除法）结合逆元的概念。首先，通过连续不断地做x = a, y = b, x = x xor y的操作，直到y变为0。此时，x就得到了原问题中两数的最大公约数。而在这个过程中，a作为原始值，需要计算它的逆元mod y，使得(a * inv_y) % y == 1。逆元inv_y可以通过扩展欧几里得算法得到，它是满足上述条件的一个数。

以下是C++使用这种方法实现求最大公约数的伪代码：

int extendedEuclidean(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = extendedEuclidean(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

// 使用逆元求最大公约数
int gcdWithXor(int a, int b) {
    int x, y;
    int gcd = extendedEuclidean(a, b, x, y);
    // 计算a的逆元mod b
    int inv_a = x % b + (b % x != 0 ? b : 0); // 如果b不是a的倍数，则加上b
    return gcd == 1 ? inv_a : gcd; // 因为gcd为1说明已经是互质，直接返回逆元
}