小编Swa*_*hIn的帖子

例如:

int get(int i) {
    int res = 0;
    while (i) {
        res = (res + tree[i]) % MOD;
        i -= ( (i) & (-i) );
    }
    return res;
}

树更新功能:

void update(int i, int val) {
    while (i <= m) {
        tree[i] = (tree[i] + val) % MOD;
        i += ( (i) & (-i) );
    }
}

你能用它解释一下他们在代码中做了什么( (i) & (-i) )吗？

我知道什么是扩展欧几里得算法以及为什么在编程中使用它。这是一种非常有用的算法，用于查找数字的逆模。我知道如何在 C++ 中实现它，这就是我在下面在 C++ 中实现它的方式。

typedef pair<int, int> pii;

#define x first
#define y second

pii extendedEuclidean(int a, int b)
{
    if(b==0)
        return {a,0};
    else {
        pii d = extendedEuclidean(b, a%b);
        return {d.y, d.x - (d.y*(a/b))};
    }
}

现在，如果我想找到一个数字的反模，例如 13，其中 mod 是例如 1000007，那么我只需调用这个函数

pair<int, int> res = extendedEuclidean(13, 1000007);

那么结果是

res.first

我的问题是为什么以及在这个递归中究竟发生了什么？以及为什么它会产生正确的结果。

注意：这里 gcd(a, b) 必须是 1。