Рубрики

Модульное мультипликативное обратное от 1 до n

Дайте положительное целое число n, найдите модульную мультипликативную инверсию всех целых чисел от 1 до n относительно большого простого числа, скажем, «простого».

Модульный мультипликативный обратный к а является целым числом «х» таким, что.

 a x ≡ 1 (mod prime) 

Примеры :

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

Простое решение состоит в том, чтобы один за другим найти модульное обратное для каждого числа.

C ++

// C ++ программа для поиска модульной инверсии
// все числа от 1 до n, использующие наивный
// метод
#include<iostream>

using namespace std;

   
// Наивный метод поиска модульного
// мультипликативный обратный к 'a'
// по модулю 'премьер'

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) << " ";

}

   
// Программа для водителя

int main()

{

    int n = 10, prime = 17;

    printModIverses(n, prime);

    return 0;

}

Джава

// Java-программа для поиска модульной инверсии
// все числа от 1 до n, использующие наивный
// метод

import java.io.*;

  

class GFG {

      

    // Наивный метод поиска модульного

    // мультипликативный обратный к 'a'

    // по модулю 'премьер'

    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) + " ");

    }

      

    // Программа для водителя

    public static void main(String args[])

    {

        int n = 10, prime = 17;

        printModIverses(n, prime);

    }

}

  

  
// Этот код предоставлен Никитой Тивари.

python3

# Python 3 программа для поиска
# модульная инверсия
# все номера от 1
# на использование наивного
# метод

  

  
# Наивный способ найти модульный
# мультипликативное обратное к 'a'
# по модулю 'премьер'

  

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= " ")

    
# Драйверная программа

n = 10

prime = 17

  
printModIverses(n, prime)

  
# Этот код добавлен
# Никита Тивари.

C #

// C # программа для поиска модульной инверсии
// все числа от 1 до n, использующие наивный
// метод

using System;

  

class GFG {

      

    // Наивный метод поиска модульного

    // мультипликативный обратный к 'a'

    // по модулю 'премьер'

    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) + " ");

    }

      

    // Программа для водителя

    public static void Main()

    {

        int n = 10, prime = 17;

          

        printModIverses(n, prime);

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа для поиска модульной инверсии
// все числа от 1 до n, использующие наивный
// метод

  
// Наивный метод поиска модульного
// мультипликативный обратный к 'a'
// по модулю 'премьер'

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) , " ";

}

  
// Программа для водителя

  

    $n = 10; $prime = 17;

    printModIverses($n, $prime);

  
// Этот код предоставлен anuj_67.
?>


Выход:

1 9 6 13 7 3 5 15 2 12

Эффективное решение основано на расширенном алгоритме Евклида .

Расширенный евклидов алгоритм дает целочисленные коэффициенты x и y такие, что:

  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) 
 

Мы можем рекурсивно найти x, используя выражение ниже (подробности см. В расширенном алгоритме Евклида ).

Расширенный алгоритм Евклида обновляет результаты gcd (a, b), используя результаты, вычисленные с помощью рекурсивного вызова gcd (b% a, a). Пусть значения x и y, вычисленные по рекурсивному вызову, будут x prev и y prev . x и y обновляются с использованием приведенных ниже выражений.

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

Мы используем вышеупомянутое отношение для вычисления обратного, используя ранее вычисленные значения.

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

Мы используем подход динамического программирования, который использует выше рекурсивную структуру.

Динамический подход:
дп [1] = 1,
дп [2] = дп [17% 2] * (17-17 / 2)% 17 = 9
дп [3] = дп [17% 3] * (17-17 / 3)% 17 = 6

и так далее..

C ++

// код CPP для поиска модульного обратного
// от 1 до n по большому простому числу
#include <iostream>

using namespace std;

  
// Функция для расчета модульной
// инвертировать с использованием DP

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] << ' ';    

}

  
// Код драйвера

int main()

{

    int n = 10, prime = 17;

    modularInverse(n, prime);

    return 0;

}

Джава

// Java-код для поиска модульного обратного
// от 1 до n по большому простому числу

import java.io.*;

  

class GFG {

  

    // Функция для расчета модульной

    // инвертировать с использованием DP

    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] + " "); 

    }

  

    // Программа для водителя

    public static void main(String args[])

    {

        int n = 10, prime = 17;

        modularInverse(n, prime);

    }

}

  

  
// Этот код предоставлен Никитой Тивари.

python3

# Python 3 код для поиска
# модульная обратная
# от 1 до n относительно
# большое простое число

  
# Функция для расчета модульной
# обратное использование DP

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=" ")

          

   
# Код драйвера

n = 10

prime = 17

  
modularInverse(n, prime)

  
# Этот код добавлен
# Никита Тивари.

C #

// C # код для поиска модульного обратного
// от 1 до n по большому простому числу

using System;

  

class GFG {

  

    // Функция для расчета модульной

    // инвертировать с использованием DP

    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] + " "); 

    }

  

    // Программа для водителя

    public static void Main()

    {

        int n = 10, prime = 17;

          

        modularInverse(n, prime);

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP-код для поиска модульного
// обратный от 1 до n относительно
// большое простое число

  
// Функция для расчета
// модульное обращение с использованием DP

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].' '); 

}

  
// Код драйвера

$n = 10; $prime = 17;

modularInverse($n, $prime);

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)
?>


Выход:

1 9 6 13 7 3 5 15 2 12

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Рекомендуемые посты:

Модульное мультипликативное обратное от 1 до n

0.00 (0%) 0 votes