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

本文概述

C ++
Java
Python3
C#
的PHP
C ++
Java
Python3
C#
的PHP

给出一个正整数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 xreturn - 1def printModIverses(n, prime) : for i in range ( 1 , n + 1 ) : print ( modInverse(i, prime) , end = " " )# Driver Program n = 10 prime = 17printModIverses(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 //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 = 1Since 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

我们使用使用上述递归结构的动态规划方法。
动态方法：
【算法设计（从1到n的模乘逆）】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 = 17modularInverse(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 //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) ?>

输出如下：