Número menor más cercano a N que tiene inverso multiplicativo bajo módulo N igual a ese número

Dado un número primo N , la tarea es encontrar el número menor más cercano que N tal que el módulo inverso multiplicativo de un número bajo el módulo N sea igual al número mismo.

Ejemplos:

Entrada: N = 7
Salida: 6
Explicación:
Módulo inverso multiplicativo de todos los números naturales posibles de 1 a menos de N son:
Módulo inverso multiplicativo de 1 bajo módulo N(=7) es 1.
Módulo inverso multiplicativo de 2 bajo módulo N( =7) es 4.
Módulo inverso multiplicativo de 3 bajo módulo N(=7) es 5.
Módulo inverso multiplicativo de 4 bajo módulo N(=7) es 2.
Módulo inverso multiplicativo de 5 bajo módulo N(=7) es 3
Módulo inverso multiplicativo de 6 bajo módulo N(=7) es 6. Por lo tanto, el
número más pequeño más cercano a N(= 7) que tiene módulo inverso igual al número mismo es 6.

Entrada: N = 11
Salida: 10

Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar todos los números naturales de 1 a N y encontrar el número más grande tal que el módulo inverso multiplicativo del número bajo el módulo N sea igual al número mismo.

Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)

Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:

El número más pequeño más cercano a N que tiene un módulo inverso multiplicativo igual al número mismo es (N – 1) .

Prueba matemática:
si X e Y son dos números tales que (X * Y) % N = 1 mod(N), entonces Y es módulo inverso de X.
Ponga X = N – 1 entonces
=>((N – 1) * Y) % N = 1 mod(N)
=>(N × Y) % N – Y % N = 1 mod(N)
=> Y = N – 1 
Por lo tanto, para X = N – 1 el valor de Y es igual a x

Por lo tanto, para resolver el problema, simplemente imprima N – 1 como la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the nearest
// smaller number satisfying
// the condition
int clstNum(int N)
{
    return (N - 1);
}
 
// Driver Code
int main()
{
    int N = 11;
    cout << clstNum(N);
}

// Java program to implement
// the above approach
import java.io.*;
 
class GFG{
 
// Function to find the nearest
// smaller number satisfying
// the condition
static int clstNum(int N){ return (N - 1); }
 
// Driver Code
public static void main(String[] args)
{
    int N = 11;
     
    System.out.println(clstNum(N));
}
}
 
// This code is contributed by akhilsaini

# Python3 program to implement
# the above approach
 
# Function to find the nearest
# smaller number satisfying
# the condition
def clstNum(N):
  return (N - 1)
 
# Driver Code
if __name__ == '__main__':
   
  N = 11
   
  print(clstNum(N))
     
# This code is contributed by akhilsaini

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to find the nearest
// smaller number satisfying
// the condition
static int clstNum(int N){ return (N - 1); }
 
// Driver Code
public static void Main()
{
    int N = 11;
     
    Console.Write(clstNum(N));
}
}
 
// This code is contributed by akhilsaini

<script>
// Javascript program to implement
// the above approach
 
// Function to find the nearest
// smaller number satisfying
// the condition
function clstNum(N)
{
    return (N - 1);
}
 
// Driver Code
let N = 11;
document.write(clstNum(N));
 
// This code is contributed by subham348.
</script>

10

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)