使用 MOD 操作将大数字映射到唯一数字

Question

令一次多项式 (Q(x)) 的根为 x0 = -b/a。由于变量 a 和 b 的范围很大，因此 x0 也可以很大，以便将其存储在变量 (x0) 中。

因此，使用 mod

的一些操作将其转换为某个唯一数字

int x0 = mul(mod - b, rev(a));

有人可以解释一下这行代码是如何工作的以及这个操作背后的数学原理吗？

整个代码-

#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

const int mod = 1e9 + 7;

int udd(int &a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int add(int a, int b) {
    return udd(a, b);
}

int mul(ll a, ll b) {
    return a * b % mod;
}

//============didnt understand this step
int bin(int a, int d) {
    int b = 1;
    while (d) {
        if (d & 1)
            b = mul(b, a);
        d >>= 1;
        a = mul(a, a);
    }
    return b;
}

int rev(int a) {
    assert(a != 0);
    return bin(a, mod - 2);
}



const int maxn = 100100;
int px[maxn];
int c[maxn];

struct Fenwick {
    int a[maxn];
    int t[maxn];

    void set(int pos, int val) {
        int delta = add(val, mod - a[pos]);
        a[pos] = val;
        delta = mul(delta, px[pos]);
        for (int i = pos; i < maxn; i |= i + 1) {
            udd(t[i], delta);
        }
    }

    int get(int r) {
        int res = 0;
        for (int i = r - 1; i >= 0; i = (i & (i + 1)) - 1)
            udd(res, t[i]);
        return res;
    }

    int get(int l, int r) {
        return add(get(r), mod - get(l));
    }
} fw;

int main() {
    #ifdef LOCAL
    assert(freopen("test.in", "r", stdin));
    #endif
    int n, a, b, q;
    cin >> n >> a >> b >> q;

    //========what does this line do?
    int x0 = mul(mod - b, rev(a));
    px[0] = 1;
    for (int i = 1; i < n; ++i)
        px[i] = mul(px[i - 1], x0);
    forn (i, n) {
        cin >> c[i];
        fw.set(i, c[i]);
    }
    forn (i, q) {
        int t, a, b;
        cin >> t >> a >> b;
        if (t == 1) {
            fw.set(a, b);
        } else {
            ++b;
            int s = fw.get(a, b);
            if (x0 == 0)
                s = fw.a[a];
            cout << (s == 0 ? "Yes" : "No") << '\n';
        }
    }
}

Answer 1

bin 是（在本例中为模）幂函数 a^d % mod 的 halving-and-squaring 实现，因此 rev 中的模逆可以通过费马小定理.

使用 MOD 操作将大数字映射到唯一数字

Mapping a large number to a unique number using MOD operation

algorithm

math

modulo

integer-division

mod