本文概述
- C ++
- Java
- Python3
- C#
- 的PHP
- C ++
- Java
- Python3
- C#
- 的PHP
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#
//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#
//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)
推荐阅读
- 模幂(模运算中的幂)
- 循环冗余校验和Modulo-2分区
- 算法题(模数10 ^ 9 + 7(1000000007))
- 自学一年C#(WPF),第二年自学Android。登录
- Android性能优化系列之渲染优化
- android studio 学习之一
- Android中使用findViewByMe提升组件查找效率
- Android NDK: Are you sure your NDK_MODULE_PATH variable is properly defined
- Android学习总结(十三) ———— ListView 简单用法