MOD演算を使用して一意の数値に大きな数値をマッピングする

Question

第1次多項式（Q（x））の根をx0 = -b/aとします。変数aとbの範囲が大きいので、変数x0に格納するためにx0を大きくすることもできます。このコード行がどのように機能するかhackerank problem

誰かが説明していただけますと数学：

ので、それがMOD

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

問題リンクに何らかの操作を使用して、いくつかのユニークな番号に変換され、この操作の後ろに？

revモジュラー逆少し定理を介して計算することができるように、全体コード -

#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用半減アンド二乗実装でありますフェルマーの