1

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

因此，使用mod的一些操作将它转换为一些唯一的数字

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

问题链接：hackerank问题

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

整个代码-

#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';
        }
    }
}
4

1 回答 1

2

bin是（在这种情况下为模）幂函数的减半平方实现，因此可以通过费马的小定理计算a^d % mod模逆。rev

于 2017-01-20T08:26:01.330 回答