Cómo convertir la probabilidad P/Q en P⋅Q-1 donde Q es coprimo con mod

Question

Yo estaba tratando con la probabilidad en la programación, pero me quedé atascado en la parte de la respuesta final.

A continuación se muestra en qué formato tengo que dar la respuesta

¿Puedes hallar las probabilidades Se puede demostrar que para cada uno de estos valores, la probabilidad se puede expresar como una fracción PQ, donde P y Q son números enteros (P0, Q>0) y Q es coprimo con 998.244.353. Debes calcular PQ1 módulo 998.244.353 para cada uno de estos valores.

A continuación se muestra la probabilidad de que se puede calcular en papel y 2 ª línea es para lo que tengo que imprimir puede explicar any1 cómo debe calcular P.Q-1.

For 1st Input
Calculated Probability = 1/4 
Answer : 748683265
For 2nd Input
Calculated Probability was = 1/16 , 3/16 , 3/16 , 9/16
Answer that was given = 436731905 935854081 811073537 811073537

Si algo no está claro entonces pls comentario como iam nuevo en la comunidad no soy muy bueno en hacer preguntas. Gracias por su respuesta de antemano.

Answer 1

$$\frac{p}{q} \equiv p \cdot q^{-1} \mod 998244353$$

Desde $q$ es coprimo con $998244353$ , $q^{-1}$ siempre existen. Se puede encontrar utilizando el algoritmo euclidiano extendido, que se muestra aquí .

Por ejemplo, $\frac{1}{4} \equiv 4^{-1} \mod 998244353$ .

Puede comprobar que $4 \cdot 748683265 = 2994733060 \equiv 1 \mod 998244353$ ,

así que $4^{-1} \equiv 748683265 \mod 998244353$ .

Answer 2

Funciona cuando m y a son coprimos

La idea es utilizar Algoritmos euclidianos ampliados que toma dos enteros 'a' y 'b', encuentra su gcd y también encuentra 'x' e 'y' tales que

ax + by = gcd(a, b)

Para encontrar la inversa multiplicativa de 'a' bajo 'm', ponemos b = m en la fórmula anterior. Como sabemos que a y m son relativamente primos, podemos poner el valor de gcd como 1.

ax + my = 1 Si tomamos el módulo m en ambos lados, obtenemos

ax + my ≡ 1 (mod m)

Podemos eliminar el segundo término del lado izquierdo ya que 'mi (mod m)' siempre sería 0 para un entero y.

ax ≡ 1 (mod m)

Así que la 'x' que podemos encontrar usando el Algoritmo Extendido de Euclides es la inversa multiplicativa de 'a'.

Código:

Código modular inverso multiplicativo

Answer 3

P=998244353; int potencia(int x, int y, int p) { int res = 1; // Inicializar resultado

x = x % p;  // Update x if it is more than or 
            // equal to p 

while (y > 0) 
{ 
    // If y is odd, multiply x with result 
    if (y & 1) 
        res = (res*x) % p; 

    // y must be even now 
    y = y>>1; // y = y/2 
    x = (x*x) % p; 
} 
return res; 

}

// Devuelve n^(-1) mod p int modInverso(int n, int p) { devuelve potencia(n, p-2, p); }

Answer 4

Esto puede resolverse utilizando Algoritmo euclidiano ampliado . Puede visitar el siguiente enlace para obtener más información y soluciones de código:

https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/

También hay un misma pregunta en desbordamiento para esto.