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

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

## 本文概述

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有效的解决方案是根据扩展欧几里得算法.

``````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 = 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``