算法设计：从1到n的模乘逆

2021年5月3日17:03:33 发表评论 951 次浏览

本文概述

给出一个正整数n, 找到模乘逆相对于较大的质数(例如"素数")从1到n的所有整数。

a的模乘逆是整数" x", 使得。

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++ 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

//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.

Python3

# 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#

//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
//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.
?>

输出如下：

1 9 6 13 7 3 5 15 2 12

An有效的解决方案是根据扩展欧几里得算法.

扩展的欧几里得算法找到整数系数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(b％a, a)计算的结果来更新gcd(a, b)的结果。设递归调用计算的x和y的值为x上一个和y上一个。使用以下表达式更新x和y。

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

我们使用上面的关系来使用先前计算的值来计算逆。

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

我们使用使用上述递归结构的动态规划方法。

动态方法：

dp [1] = 1

dp [2] = dp [17％2] *(17-17/2)％17 = 9

dp [3] = dp [17％3] *(17-17/3)％17 = 6

等等..

C ++

//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

//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.

Python3

# 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#

//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
//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)
?>

输出如下：

1 9 6 13 7 3 5 15 2 12

时间复杂度：O(N)

辅助空间：O(N)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: