Dados tres enteros positivos A , B y N , que representan una congruencia lineal de la forma AX=B (mod N), la tarea es imprimir todos los valores posibles de X (mod N) , es decir, en el rango [0, N -1] que satisface esta ecuación. Si no hay solución, imprima -1.
Ejemplos:
Entrada: A=15, B=9, N=18
Salida: 15, 3, 9
Explicación: Los valores de X que satisfacen la condición AX=B (mod N) son {3, 9, 15}.
(15*15)%18 = 225%18=9
(3*15)%18 = 45%18=9
(9*15)%18 = 135%18=9Entrada: A=9, B=21, N=30
Salida: 9, 19, 20
Enfoque: La idea se basa en las siguientes observaciones:
- Existe una solución si y solo si B es divisible por GCD (A, N), es decir , B% GCD (A, N) = 0 .
- El número de soluciones para X (mod N) es GCD(A, N) .
Prueba:
- Dado, AX=B (mod N)
⇒ existe un número Y tal que AX=B+NY
AX-NY=B — (1)
Esta es una ecuación diofántica lineal , y es resoluble si y solo si MCD(A, N ) divide B .- Ahora, utilizando el Algoritmo Euclidiano Extendido, u y v se pueden encontrar tales que Au+Nv=GCD(A, N)=d (digamos)
⇒ Au+Nv=d
⇒ Au=d (mod N) — (2)- Suponiendo que B%d=0 , de modo que exista la solución de la Ecuación 1,
Multiplicando ambos lados de la Ecuación 2 por B/d , (posible ya que B/d es un número entero),
Au*(B/d)=d*(B/ d) (mod N) o A*(u*B/d)=B (mod N) .
Por lo tanto, u*B/d es una solución de la Ecuación 1.- Sea X0 u *B/d .
Así, las d soluciones de la Ecuación 1 serán X0, X0+(N/d), X0+2*(N/d), …, X0+(d-1)*(N/d)
Siga los pasos a continuación para resolver el problema:
- Inicialice la variable d como GCD(A, N) así como u usando el Algoritmo Euclidiano Extendido .
- Si B no es divisible por d , imprima -1 como resultado.
- De lo contrario , iterar en el rango [0, d-1] usando la variable i y en cada iteración imprimir el valor de u*(B/d)+i*(N/d) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to stores the values of x and y
// and find the value of gcd(a, b)
long long ExtendedEuclidAlgo(
long long a, long long b,
long long& x, long long& y)
{
// Base Case
if (b == 0) {
x = 1;
y = 0;
return a;
}
else {
// Store the result of recursive call
long long x1, y1;
long long gcd
= ExtendedEuclidAlgo(b, a % b, x1, y1);
// Update x and y using results of
// recursive call
x = y1;
y = x1 - floor(a / b) * y1;
return gcd;
}
}
// Function to give the distinct
// solutions of ax = b (mod n)
void linearCongruence(long long A,
long long B,
long long N)
{
A = A % N;
B = B % N;
long long u = 0, v = 0;
// Function Call to find
// the value of d and u
long long d = ExtendedEuclidAlgo(A, N, u, v);
// No solution exists
if (B % d != 0) {
cout << -1 << endl;
return;
}
// Else, initialize the value of x0
long long x0 = (u * (B / d)) % N;
if (x0 < 0)
x0 += N;
// Print all the answers
for (long long i = 0; i <= d - 1; i++)
cout << (x0 + i * (N / d)) % N << " ";
}
// Driver Code
int main()
{
// Input
long long A = 15;
long long B = 9;
long long N = 18;
// Function Call
linearCongruence(A, B, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to stores the values of x and y
// and find the value of gcd(a, b)
public static long[] ExtendedEuclidAlgo(long a,
long b)
{
// Base Case
if (a == 0)
{
return new long[]{b, 0, 1};
}
else
{
// Store the result of recursive call
long x1 = 1, y1 = 1;
long gcdy[] = ExtendedEuclidAlgo(b % a, a);
long gcd = gcdy[0];
x1 = gcdy[1];
y1 = gcdy[2];
// Update x and y using results of
// recursive call
long y = x1;
long x = y1 - (long)Math.floor(b / a) * x1;
return new long[] {gcd, x, y};
}
}
// Function to give the distinct
// solutions of ax = b (mod n)
public static void linearCongruence(long A,
long B,
long N)
{
A = A % N;
B = B % N;
long u = 0, v = 0;
// Function Call to find
// the value of d and u
long person[] = ExtendedEuclidAlgo(A, N);
long d = person[0];
u = person[1];
v = person[2];
// No solution exists
if (B % d != 0)
{
System.out.println(-1);
return;
}
// Else, initialize the value of x0
long x0 = (u * (B / d)) % N;
if (x0 < 0)
x0 += N;
// Print all the answers
for(long i = 0; i <= d - 1; i++)
{
long an = (x0 + i * (N / d)) % N;
System.out.print(an + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Input
long A = 15;
long B = 9;
long N = 18;
// Function Call
linearCongruence(A, B, N);
}
}
// This code is contributed by Shubhamsingh10
Python3
# Python3 program for the above approach # Function to stores the values of x and y # and find the value of gcd(a, b) def ExtendedEuclidAlgo(a, b): # Base Case if a == 0 : return b, 0, 1 gcd, x1, y1 = ExtendedEuclidAlgo(b % a, a) # Update x and y using results of recursive # call x = y1 - (b // a) * x1 y = x1 return gcd, x, y # Function to give the distinct # solutions of ax = b (mod n) def linearCongruence(A, B, N): A = A % N B = B % N u = 0 v = 0 # Function Call to find # the value of d and u d, u, v = ExtendedEuclidAlgo(A, N) # No solution exists if (B % d != 0): print(-1) return # Else, initialize the value of x0 x0 = (u * (B // d)) % N if (x0 < 0): x0 += N # Pr all the answers for i in range(d): print((x0 + i * (N // d)) % N, end = " ") # Driver Code # Input A = 15 B = 9 N = 18 # Function Call linearCongruence(A, B, N) # This code is contributed by SHUBHAMSINGH10
C#
// C# program for the above approach
using System;
class GFG{
// Function to stores the values of x and y
// and find the value of gcd(a, b)
public static long[] ExtendedEuclidAlgo(long a,
long b)
{
// Base Case
if (a == 0)
{
return new long[]{b, 0, 1};
}
else
{
// Store the result of recursive call
long x1 = 1, y1 = 1;
long[] gcdy = ExtendedEuclidAlgo(b % a, a);
long gcd = gcdy[0];
x1 = gcdy[1];
y1 = gcdy[2];
// Update x and y using results of
// recursive call
long y = x1;
long x = y1 - (long)(b / a) * x1;
return new long[] {gcd, x, y};
}
}
// Function to give the distinct
// solutions of ax = b (mod n)
public static void linearCongruence(long A,
long B,
long N)
{
A = A % N;
B = B % N;
long u = 0, v = 0;
// Function Call to find
// the value of d and u
long []person = ExtendedEuclidAlgo(A, N);
long d = person[0];
u = person[1];
v = person[2];
// No solution exists
if (B % d != 0)
{
Console.WriteLine(-1);
return;
}
// Else, initialize the value of x0
long x0 = (u * (B / d)) % N;
if (x0 < 0)
x0 += N;
// Print all the answers
for(long i = 0; i <= d - 1; i++)
{
long an = (x0 + i * (N / d)) % N;
Console.Write(an + " ");
}
}
// Driver Code
static public void Main (){
// Input
long A = 15;
long B = 9;
long N = 18;
// Function Call
linearCongruence(A, B, N);
}
}
// This code is contributed by Shubhamsingh10
Javascript
<script>
// JavaScript program for the above approach
// Function to stores the values of x and y
// and find the value of gcd(a, b)
function ExtendedEuclidAlgo(a, b)
{
// Base Case
if (a == 0)
{
return [b, 0, 1];
}
else
{
// Store the result of recursive call
let x1 = 1, y1 = 1;
let gcdy = ExtendedEuclidAlgo(b % a, a);
let gcd = gcdy[0];
x1 = gcdy[1];
y1 = gcdy[2];
// Update x and y using results of
// recursive call
let y = x1;
let x = y1 - Math.floor(b / a) * x1;
return [gcd, x, y];
}
}
// Function to give the distinct
// solutions of ax = b (mod n)
function linearCongruence(A, B, N)
{
A = A % N;
B = B % N;
let u = 0, v = 0;
// Function Call to find
// the value of d and u
let person = ExtendedEuclidAlgo(A, N);
let d = person[0];
u = person[1];
v = person[2];
// No solution exists
if (B % d != 0)
{
document.write(-1);
return;
}
// Else, initialize the value of x0
let x0 = (u * (B / d)) % N;
if (x0 < 0)
x0 += N;
// Print all the answers
for(let i = 0; i <= d - 1; i++)
{
let an = (x0 + i * (N / d)) % N;
document.write(an + " ");
}
}
// Driver Code
// Input
let A = 15;
let B = 9;
let N = 18;
// Function Call
linearCongruence(A, B, N);
// This code is contributed by sanjoy_62.
</script>
Producción
15 3 9
Complejidad de tiempo: O(log(min(A, N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sourashis69 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA