Inverso multiplicativo modular de 1 a n

Da un entero positivo n, encuentra el inverso multiplicativo modular de todos los enteros del 1 al n con respecto a un número primo grande, digamos, ‘primo’.

El inverso multiplicativo modular de a es un entero ‘x’ tal que. 

 a x ≡ 1 (mod prime) 

Ejemplos: 

Input : n = 10, prime = 17
Output : 1 9 6 13 7 3 5 15 2 12
Explanation :
For 1, modular inverse is 1 as (1 * 1)%17 is 1
For 2, modular inverse is 9 as (2 * 9)%17 is 1
For 3, modular inverse is 6 as (3 * 6)%17 is 1
....... 

Input : n = 5, prime = 7
Output : 1 4 5 2 3

Una solución simple es encontrar uno por uno el inverso modular para cada número. 

// C++ program to find modular inverse of
// all numbers from 1 to n using naive
// method
#include<iostream>
using namespace std;
  
// A naive method to find modular
// multiplicative inverse of 'a'
// under modulo 'prime'
int modInverse(int a, int prime)
{
    a = a % prime;
    for (int x=1; x<prime; x++)
       if ((a*x) % prime == 1)
          return x;
      
    return -1;
}
 
void printModIverses(int n, int prime)
{
    for (int i=1; i<=n; i++)
      cout << modInverse(i, prime) << " ";
}
  
// Driver Program
int main()
{
    int n = 10, prime = 17;
    printModIverses(n, prime);
    return 0;
}

// Java program to find modular inverse of
// all numbers from 1 to n using naive
// method
import java.io.*;
 
class GFG {
     
    // A naive method to find modular
    // multiplicative inverse of 'a'
    // under modulo 'prime'
    static int modInverse(int a, int prime)
    {
        a = a % prime;
        for (int x = 1; x  <prime; x++)
        if ((a * x) % prime == 1)
            return x;
         
        return -1;
    }
     
    static void printModIverses(int n, int prime)
    {
        for (int i = 1; i <= n; i++)
        System.out.print(modInverse(i, prime) + " ");
    }
     
    // Driver Program
    public static void main(String args[])
    {
        int n = 10, prime = 17;
        printModIverses(n, prime);
    }
}
 
 
// This code is contributed by Nikita Tiwari.

# Python 3 program to find
# modular inverse of
# all numbers from 1
# to n using naive
# method
 
 
# A naive method to find modular
# multiplicative inverse of 'a'
# under modulo 'prime'
 
def modInverse(a, prime) :
    a = a % prime
    for x in range(1,prime) :
        if ((a*x) % prime == 1) :
            return x
       
    return -1
     
  
def printModIverses(n, prime) :
    for i in range(1,n+1) :
        print( modInverse(i, prime) ,end= " ")
   
# Driver Program
n = 10
prime = 17
 
printModIverses(n, prime)
 
# This code is contributed
# by Nikita Tiwari.

// C# program to find modular inverse of
// all numbers from 1 to n using naive
// method
using System;
 
class GFG {
     
    // A naive method to find modular
    // multiplicative inverse of 'a'
    // under modulo 'prime'
    static int modInverse(int a, int prime)
    {
        a = a % prime;
        for (int x = 1; x <prime; x++)
            if ((a * x) % prime == 1)
                return x;
         
        return -1;
    }
     
    static void printModIverses(int n, int prime)
    {
        for (int i = 1; i <= n; i++)
            Console.Write(modInverse(i, prime) + " ");
    }
     
    // Driver Program
    public static void Main()
    {
        int n = 10, prime = 17;
         
        printModIverses(n, prime);
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find modular inverse of
// all numbers from 1 to n using naive
// method
 
// A naive method to find modular
// multiplicative inverse of 'a'
// under modulo 'prime'
function modInverse(int $a, int $prime)
{
    $a = $a % $prime;
    for ( $x = 1; $x < $prime; $x++)
    if (($a * $x) % $prime == 1)
        return $x;
     
    return -1;
}
 
function printModIverses( $n, $prime)
{
    for ( $i = 1; $i <= $n; $i++)
    echo modInverse($i, $prime) , " ";
}
 
// Driver Program
 
    $n = 10; $prime = 17;
    printModIverses($n, $prime);
 
// This code is contributed by anuj_67.
?>

<script>
 
// Javascript program to find modular
// inverse of all numbers from 1 to n
// using naive method
 
// A naive method to find modular
// multiplicative inverse of 'a'
// under modulo 'prime'
function modInverse(a, prime)
{
    a = a % prime;
     
    for(let x = 1; x < prime; x++)
        if ((a * x) % prime == 1)
            return x;
     
    return -1;
}
 
function printModIverses( n, prime)
{
    for(let i = 1; i <= n; i++)
        document.write(modInverse(i, prime) + " ");
}
 
// Driver code
let n = 10;
let prime = 17;
 
printModIverses(n, prime);
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Producción: 

1 9 6 13 7 3 5 15 2 12

Una solución eficiente se basa en el algoritmo de Euclides extendido .
El algoritmo euclidiano extendido encuentra coeficientes enteros x e y tales que: 

  ax + by = gcd(a, b)

Let us put b = prime, we get
  ax + prime * y = gcd(a, prime)

We know gcd(a, prime) = 1 because
on of the numbers is prime. So we
know
  ax + prime * y = 1

Since prime * y is a multiple of prime,
x is modular multiplicative inverse of a.

 ax  ≡ 1 (mod prime) 
 

Podemos encontrar recursivamente x usando la siguiente expresión (consulte el algoritmo de Euclides extendido para obtener más detalles).
El algoritmo euclidiano extendido actualiza los resultados de gcd(a, b) usando los resultados calculados por la llamada recursiva gcd(b%a, a). Deje que los valores de x e y calculados por la llamada recursiva sean x _prev e y _prev . x e y se actualizan usando las siguientes expresiones. 

x = yprev - ⌊prime/a⌋ * xprev
y = xprev

Usamos la relación anterior para calcular la inversa usando valores calculados previamente. 
 

inverse(a) = (inverse(prime % a) *
              (prime - prime/a)) % prime

Utilizamos el enfoque de programación dinámica que utiliza la estructura recursiva anterior.
Enfoque dinámico: 
dp[1] = 1, 
dp[2] = dp[17%2]*(17-17/2)%17 = 9 
dp[3] = dp[17%3]*(17-17/ 3)%17 = 6
y así sucesivamente..

// CPP code to find modular inverse
// from 1 to n w.r.t a big prime number
#include <iostream>
using namespace std;
 
// Function to calculate modular
// inverse using D.P
void modularInverse(int n, int prime)
{
    int dp[n + 1];
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[prime % i] *
               (prime - prime / i) % prime;   
 
    for (int i = 1; i <= n; i++)
        cout << dp[i] << ' ';   
}
 
// Driver code
int main()
{
    int n = 10, prime = 17;
    modularInverse(n, prime);
    return 0;
}

// Java code to find modular inverse
// from 1 to n w.r.t a big prime number
import java.io.*;
 
class GFG {
 
    // Function to calculate modular
    // inverse using D.P
    static void modularInverse(int n, int prime)
    {
        int dp[]=new int[n + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++)
            dp[i] = dp[prime % i] *
                (prime - prime / i) % prime;
     
        for (int i = 1; i <= n; i++)
            System.out.print(dp[i] + " ");
    }
 
    // Driver Program
    public static void main(String args[])
    {
        int n = 10, prime = 17;
        modularInverse(n, prime);
    }
}
 
 
// This code is contributed by Nikita Tiwari.

# Python 3 code to find
# modular inverse
# from 1 to n w.r.t a
# big prime number
 
# Function to calculate modular
# inverse using D.P
def modularInverse( n, prime) :
 
    dp =[0]*(n+1)
    dp[0] = dp[1] = 1
    for i in range( 2, n+1) :
        dp[i] = dp[prime % i] *(prime - prime // i) % prime
  
    for i in range( 1, n+1) :
        print(dp[i] ,end=" ")
         
  
# Driver code
n = 10
prime = 17
 
modularInverse(n, prime)
 
# This code is contributed
# by Nikita Tiwari.

// C# code to find modular inverse
// from 1 to n w.r.t a big prime number
using System;
 
class GFG {
 
    // Function to calculate modular
    // inverse using D.P
    static void modularInverse(int n, int prime)
    {
        int []dp=new int[n + 1];
        dp[0] = dp[1] = 1;
         
        for (int i = 2; i <= n; i++)
            dp[i] = dp[prime % i] *
                (prime - prime / i) % prime;
     
        for (int i = 1; i <= n; i++)
            Console.Write(dp[i] + " ");
    }
 
    // Driver Program
    public static void Main()
    {
        int n = 10, prime = 17;
         
        modularInverse(n, prime);
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP code to find modular
// inverse from 1 to n w.r.t
// a big prime number
 
// Function to calculate
// modular inverse using D.P
function modularInverse($n, $prime)
{
    $dp = array();
    $dp[0] = $dp[1] = 1;
    for ($i = 2; $i <= $n; $i++)
        $dp[$i] = $dp[$prime % $i] *
                     ($prime -
               intval($prime / $i)) %
                      $prime;
 
    for ($i = 1; $i <= $n; $i++)
        echo ($dp[$i].' ');
}
 
// Driver code
$n = 10; $prime = 17;
modularInverse($n, $prime);
 
// This code is contributed by
// Manish Shaw(manishshaw1)
?>

<script>
 
// Javascript code to find modular
// inverse from 1 to n w.r.t
// a big prime number
 
// Function to calculate
// modular inverse using D.P
function modularInverse(n, prime)
{
    let dp = [];
    dp[0] = dp[1] = 1;
     
    for(let i = 2; i <= n; i++)
        dp[i] = dp[prime % i] * (prime -
         parseInt(prime / i)) % prime;
 
    for(let i = 1; i <= n; i++)
        document.write(dp[i] + ' ');
}
 
// Driver code
let n = 10;
let prime = 17;
 
modularInverse(n, prime);
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Producción: 

1 9 6 13 7 3 5 15 2 12

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(n)