Truco para división modular ((x1*x2….xn)/b) mod (m)

Dados los enteros x1, x2, x3……xn, b y m, se supone que debemos encontrar el resultado de ((x1*x2….xn)/b)mod(m). 
Ejemplo 1: supongamos que debemos encontrar (55C5)%(1000000007) es decir ((55*54*53*52*51)/120)%1000000007 
Método ingenuo: 

1. Simplemente calcule el producto (55*54*53*52*51) = digamos x,
2. Divide x por 120 y luego toma su módulo con 1000000007

Uso del inverso multiplicativo modular: 
el método anterior funcionará solo cuando x1, x2, x3….xn tengan valores pequeños. 
Supongamos que debemos encontrar el resultado donde x1, x2, ….xn caen en el rango de ~1000000(10^6). Así que tendremos que explotar la regla de las matemáticas modulares que dice: 
(a*b)mod(m)=(a(mod(m))*b(mod(m)))mod(m)
Tenga en cuenta que la fórmula anterior es válido para la multiplicación modular. No existe una fórmula similar para la división. 
es decir (a/b)mod(m) != a(mod(m))/b(mod(m)) 

1. Por lo tanto, debemos encontrar el inverso multiplicativo modular de b, digamos i y luego multiplique ‘i’ con a.
2. Después de esto tendremos que sacar el módulo del resultado obtenido. 
   es decir ((x1*x2….xn)/b)mod(m)=((x1*x2….xn)*i)mod(m)= ((x1)mod(m) * (x2)mod(m ) *….(xn)mod(m) * (i)mod(m))mod(m)

Nota: Para encontrar el inverso multiplicativo modular podemos usar el algoritmo euclidiano extendido o el pequeño teorema de Fermat. 
Ejemplo 2: Supongamos que tenemos que encontrar (55555C5)%(1000000007) es decir ((55555*55554*55553*55552*55551)/120)%1000000007. 
 

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long  ll;
#define int ll
typedef   long double ld;
ll MOD = 998244353;
double eps = 1e-12;
#define mp make_pair
#define pb push_back
#define INF 2e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
 
int modular_inverse(int a, int m){
    for (int x = 1; x < m; x++)
        if (((a%m) * (x%m)) % m == 1)
            return x;
    return 0;
}
 
int32_t main()
{
    // naive method-calculating the result in a single line
     int ans = 1;
     int naive_answer = ((55555 *55554 *55553 *55552 * 55551)/120)% 1000000007;
 
    // modular_inverse() is a user defined function
    // that calculates inverse of a number
     int i = modular_inverse(120, 10000007);
 
    // it will use extended Euclidean algorithm or
    // Fermat’s Little Theorem for calculation.
    // MMI of 120 under division by 1000000007
    // will be 808333339
    for (int i = 0; i < 5; i++)
        ans = (ans * (55555 - i)) % 1000000007;
     
    ans = (ans * i) % 1000000007;
    cout << "Answer using naive method: " << naive_answer << endl;
    cout << "Answer using multiplicative"
         << " modular inverse concept: " << ans;
 
    return 0;
}
 
// The code is contributed by Gautam goel (gautamgoel962)

# Python3 program to implement
# the above approach
 
# multiplicative-inverse-under-modulo-m/
def modular_inverse(a, m):
      
    for x in range(1, m):
        if (((a%m) * (x%m)) % m == 1):
            return x
    return -1
 
 
if __name__ == '__main__':
     
    # naive method-calculating the
    # result in a single line
    naive_answer = (((55555 * 55554 *
                      55553 * 55552 *
                      55551) // 120) %
                      1000000007)
 
    ans = 1
 
    # modular_inverse() is a user
    # defined function that calculates
    # inverse of a number
    i = modular_inverse(120, 10000007)
 
    # it will use extended Euclidean
    # algorithm or Fermat's Little
    # Theorem for calculation.
    # MMI of 120 under division by
    # 1000000007 will be 808333339
    for j in range(5):
        ans = ((ans *
               (55555 - j)) %
                1000000007)
 
    ans = (ans * i) % 1000000007
 
    print("Answer using naive method:",
           naive_answer)
    print("Answer using multiplicative" +
          "modular inverse concept:", ans)
 
# This code is contributed by Gautam goel (gautamgoel962)

// JavaScript program to implement above approach
 
// A function to calculate the Modular
// inverse of the function
function modular_inverse(a, m){
    for(let x = 1; x < m; x++){
        if (((a % m) * (x % m)) % m == 1){
                return x;
        }
    }       
}
 
// naive method-calculating the
// result in a single line
let naive_answer =((55555 * 55554 * 55553 * 55552 * 55551) / 120) % 1000000007;
let ans = 1
 
// modular_inverse() is a user
// defined function that calculates
// inverse of a number
let i = modular_inverse(120, 10000007)
 
// it will use extended Euclidean
// algorithm or Fermat's Little
// Theorem for calculation.
// MMI of 120 under division by
// 1000000007 will be 808333339
for(let j = 0;j < 5; j++){
    ans = ((ans * (55555 - j)) % 1000000007)
}
 
ans = (ans * i) % 1000000007
 
console.log("Answer using naive method:",
        naive_answer)
console.log("Answer using multiplicative" +
        "modular inverse concept:", ans)
 
// This code is contributed by Gautam goel (gautamgoel962)

Different Languages give different result for the naive approach. 

C++
Input : 
Output:
    Answer using naive method: 18446744073703577963
    Answer using multiplicative modular inverse concept: 125376140
    
Python 
Input:
Output:
    Answer using naive method: 300820513
    Answer using multiplicative modular inverse concept: 125376140
    
JavaScript:
Input:
Output:
    Answer using naive method: 301201761
    Answer using multiplicative modular inverse concept: 125376140

Está claro del ejemplo anterior que el método ingenuo conducirá a un desbordamiento de datos que dará como resultado una respuesta incorrecta. Además, usar la inversa modular nos dará la respuesta correcta.
Sin usar el inverso multiplicativo modular: 
Pero es interesante notar que un ligero cambio en el código descartará el uso de encontrar el inverso multiplicativo modular. 
 

#include <iostream>
using namespace std;
int main()
{
    long int ans = 1;
    long int mod = (long int)1000000007 * 120;
    for (int i = 0; i < 5; i++)
        ans = (ans * (55555 - i)) % mod;   
    ans = ans / 120;
    cout << "Answer using shortcut: " << ans;
    return 0;
}

class GFG {
 
    public static void main(String[] args)
    {
        long ans = 1;
        long mod = (long)1000000007 * 120;
         
        for (int i = 0; i < 5; i++)
            ans = (ans * (55555 - i)) % mod;
             
        ans = ans / 120;
        System.out.println("Answer using"
                    + " shortcut: "+ ans);
    }
}
 
// This code is contributed by smitha.

ans = 1
mod = 1000000007 * 120
 
for i in range(0, 5) :
    ans = (ans * (55555 - i)) % mod
     
ans = int(ans / 120)
 
print("Answer using shortcut: ", ans)
 
# This code is contributed by Smitha.

using System;
 
class GFG {
 
    public static void Main()
    {
        long ans = 1;
        long mod = (long)1000000007 * 120;
         
        for (int i = 0; i < 5; i++)
            ans = (ans * (55555 - i)) % mod;
             
        ans = ans / 120;
        Console.Write("Answer using "
                    + "shortcut: "+ ans);
    }
}
 
// This code is contributed by smitha.

<?php
    $ans = 1;
    $mod = 1000000007 * 120;
     
    for ( $i = 0; $i < 5; $i++)
        $ans = ($ans * (55555 - $i)) %
                                 $mod;
    $ans = $ans / 120;
    echo "Answer using shortcut: " ,
                               $ans;
     
// This code is contributed by anuj_67.
?>

<script>
 
var ans = 1;
var mod = 1000000007 * 120;
 
for(var i = 0; i < 5; i++)
    ans = (ans * (55555 - i)) % mod;
     
ans = ans / 120;
document.write("Answer using" +
               " shortcut: "+ ans);
 
// This code is contributed by Kirti
 
</script>

Answer using shortcut: 300820513

¿Por qué funcionó?  
Esto funcionará solo en caso de que el denominador sea un factor del numerador, es decir, cuando a % b = 0 siguiendo la regla: 
Si b | a, entonces podemos escribir (a/b) % p como (a % p*b)/b. 
Esta regla resulta útil para valores pequeños de b.
Consideremos a = x1*x2*x3…….xn 
Tenemos que encontrar ans = (a/b)%1000000007 

1. Sea y el resultado de a%(1000000007*b). Para evitar el desbordamiento, usamos la propiedad multiplicativa modular. Esto se puede representar como 
   a = (1000000007*b)q + y donde y < (1000000007*b) y q es un número entero
2. Ahora dividiendo LHS y RHS por b, obtenemos 
   y/b = a/b -(1000000007*b)*q/b 
   = a/b -1000000007*q < 1000000007 (De 1) 
   Por lo tanto, y/b es equivalente a ( a/b)mod(b*1000000007). 🙂