Mappage d'un grand nombre à un nombre unique à l'aide de l'opération MOD

Question

Laisser les racines d'un polynôme du premier degré (Q (x)) être x0 = -b/a. Puisque la plage de la variable a et b est grande, x0 peut aussi être grand pour être stocké dans une variable (x0).

donc, il est converti en un nombre unique en utilisant une opération avec mod

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

lien problème: hackerank problem

Quelqu'un peut-il s'il vous plaît expliquer comment cette ligne de code fonctionne et les mathématiques derrière cette opération?

l'ensemble code-

#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 est la mise en œuvre de réduire de moitié-et-élévation au carré pour la (dans ce modulaire de cas) fonction de puissance a^d % mod, de sorte que l'inverse modulaire rev peut être calculée par l'intermédiaire du petit théorème de Fermat.