Dadas dos arrays A[] y B[] , ambas compuestas por N enteros positivos, un entero P y los elementos de la array A[] son coprimos por pares , la tarea es encontrar el entero más pequeño X que sea al menos P y X % A[i] es igual a B[i] para todo i sobre el rango de índices [0, N – 1] .
Ejemplos:
Entrada: A[] = {3, 4, 5}, B[] = {2, 3, 1}, P = 72 Salida:
131 Explicación
:
Considere las siguientes operaciones para el valor de X como 131.
- X % A[0] = 131 % 3 = 2 (= B[0])
- X % A[1] = 131 % 4 = 3 (= B[1])
- X % A[2] = 131 % 5 = 1 (= B[2])
Por lo tanto, 131 es el entero más pequeño que es al menos P( = 72).
Entrada: A[] = {5, 7}, B[] = {1, 3}, P = 0
Salida: 31
Enfoque: La idea para resolver el problema dado es usar el Teorema del Resto Chino . Siga los pasos a continuación para resolver el problema dado:
- Calcule el MCM de la array A[] , que es igual al producto de todos los elementos presentes en la array A[] , digamos M , ya que todos los elementos son coprimos .
- Usando el Teorema del Resto Chino , encuentre el entero positivo más pequeño requerido Y . Por lo tanto, el valor de X viene dado por (Y + K * M) para algún número entero K , que satisface X % A[i] = B[i] para todo i sobre el rango de índices [0, N – 1] .
- El valor de K se puede encontrar a partir de la ecuación Y + K * M >= P , que equivale a K >= (P – Y)/M .
- Por lo tanto, el entero X más pequeño posible requerido es (Y + K * M) .
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 calculate modulo
// inverse of a w.r.t m using
// Extended Euclid Algorithm
int inv(int a, int m)
{
int m0 = m, t, q;
int x0 = 0, x1 = 1;
// Base Case
if (m == 1)
return 0;
// Perform extended
// euclid algorithm
while (a > 1)
{
// q is quotient
q = a / m;
t = m;
// m is remainder now,
// process same as
// euclid's algorithm
m = a % m;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
// If x1 is negative
if (x1 < 0)
// Make x1 positive
x1 += m0;
return x1;
}
// Function to implement Chinese
// Remainder Theorem to find X
int findMinX(int A[], int B[], int N)
{
// Stores the product
// of array elements
int prod = 1;
// Traverse the array
for(int i = 0; i < N; i++)
// Update product
prod *= A[i];
// Initialize the result
int result = 0;
// Apply the above formula
for(int i = 0; i < N; i++)
{
int pp = prod / A[i];
result += B[i] * inv(pp, A[i]) * pp;
}
return result % prod;
}
// Function to calculate the product
// of all elements of the array a[]
int product(int a[], int n)
{
// Stores product of
// all array elements
int ans = 1;
// Traverse the array
for(int i = 0; i < n; i++)
{
ans *= a[i];
}
// Return the product
return ans;
}
// Function to find the value of X
// that satisfies the given condition
void findSmallestInteger(int A[], int B[],
int P, int n)
{
// Stores the required smallest value
// using Chinese Remainder Theorem
int Y = findMinX(A, B, n);
// Stores the product
// of all array elements
int M = product(A,n);
// The equation is Y + K*M >= P
// Therefore, calculate K = ceil((P-Y)/M)
int K = ceil(((double)P - (double)Y) /
(double)M);
// So, X = Y + K*M
int X = Y + K * M;
// Print the resultant value of X
cout << X;
}
// Driver Code
int main()
{
int A[] = { 3, 4, 5 };
int B[] = { 2, 3, 1 };
int n = sizeof(A) / sizeof(A[0]);
int P = 72;
findSmallestInteger(A, B, P,n);
}
// This code is contributed by SURENDRA_GANGWAR
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class Main {
// Function to calculate modulo
// inverse of a w.r.t m using
// Extended Euclid Algorithm
static int inv(int a, int m)
{
int m0 = m, t, q;
int x0 = 0, x1 = 1;
// Base Case
if (m == 1)
return 0;
// Perform extended
// euclid algorithm
while (a > 1) {
// q is quotient
q = a / m;
t = m;
// m is remainder now,
// process same as
// euclid's algorithm
m = a % m;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
// If x1 is negative
if (x1 < 0)
// Make x1 positive
x1 += m0;
return x1;
}
// Function to implement Chinese
// Remainder Theorem to find X
static int findMinX(int A[], int B[], int N)
{
// Stores the product
// of array elements
int prod = 1;
// Traverse the array
for (int i = 0; i < N; i++)
// Update product
prod *= A[i];
// Initialize the result
int result = 0;
// Apply the above formula
for (int i = 0; i < N; i++) {
int pp = prod / A[i];
result += B[i] * inv(pp, A[i]) * pp;
}
return result % prod;
}
// Function to calculate the product
// of all elements of the array a[]
static int product(int a[])
{
// Stores product of
// all array elements
int ans = 1;
// Traverse the array
for (int i = 0; i < a.length; i++) {
ans *= a[i];
}
// Return the product
return ans;
}
// Function to find the value of X
// that satisfies the given condition
public static void findSmallestInteger(int A[], int B[],
int P)
{
// Stores the required smallest value
// using Chinese Remainder Theorem
int Y = findMinX(A, B, A.length);
// Stores the product
// of all array elements
int M = product(A);
// The equation is Y + K*M >= P
// Therefore, calculate K = ceil((P-Y)/M)
int K = (int)Math.ceil(((double)P - (double)Y)
/ (double)M);
// So, X = Y + K*M
int X = Y + K * M;
// Print the resultant value of X
System.out.println(X);
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 3, 4, 5 };
int B[] = { 2, 3, 1 };
int P = 72;
findSmallestInteger(A, B, P);
}
}
Python3
# Python3 program for the above approach import math # Function to calculate modulo # inverse of a w.r.t m using # Extended Euclid Algorithm def inv(a, m): m0 = m x0 = 0 x1 = 1 # Base Case if (m == 1): return 0 # Perform extended # euclid algorithm while (a > 1): # q is quotient q = a // m t = m # m is remainder now, # process same as # euclid's algorithm m = a % m a = t t = x0 x0 = x1 - q * x0 x1 = t # If x1 is negative if (x1 < 0): # Make x1 positive x1 += m0 return x1 # Function to implement Chinese # Remainder Theorem to find X def findMinX(A, B, N): # Stores the product # of array elements prod = 1 # Traverse the array for i in range(N): # Update product prod *= A[i] # Initialize the result result = 0 # Apply the above formula for i in range(N): pp = prod // A[i] result += B[i] * inv(pp, A[i]) * pp return result % prod # Function to calculate the product # of all elements of the array a[] def product(a, n): # Stores product of # all array elements ans = 1 # Traverse the array for i in range(n): ans *= a[i] # Return the product return ans # Function to find the value of X # that satisfies the given condition def findSmallestInteger(A, B, P, n): # Stores the required smallest value # using Chinese Remainder Theorem Y = findMinX(A, B, n) # Stores the product # of all array elements M = product(A, n) # The equation is Y + K*M >= P # Therefore, calculate K = ceil((P-Y)/M) K = math.ceil((P - Y) / M) # So, X = Y + K*M X = Y + K * M # Print the resultant value of X print(X) # Driver Code if __name__ == "__main__" : A = [ 3, 4, 5 ] B = [ 2, 3, 1 ] n = len(A) P = 72 findSmallestInteger(A, B, P, n) # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to calculate modulo
// inverse of a w.r.t m using
// Extended Euclid Algorithm
static int inv(int a, int m)
{
int m0 = m, t, q;
int x0 = 0, x1 = 1;
// Base Case
if (m == 1)
return 0;
// Perform extended
// euclid algorithm
while (a > 1) {
// q is quotient
q = a / m;
t = m;
// m is remainder now,
// process same as
// euclid's algorithm
m = a % m;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
// If x1 is negative
if (x1 < 0)
// Make x1 positive
x1 += m0;
return x1;
}
// Function to implement Chinese
// Remainder Theorem to find X
static int findMinX(int[] A, int[] B, int N)
{
// Stores the product
// of array elements
int prod = 1;
// Traverse the array
for (int i = 0; i < N; i++)
// Update product
prod *= A[i];
// Initialize the result
int result = 0;
// Apply the above formula
for (int i = 0; i < N; i++) {
int pp = prod / A[i];
result += B[i] * inv(pp, A[i]) * pp;
}
return result % prod;
}
// Function to calculate the product
// of all elements of the array a[]
static int product(int[] a)
{
// Stores product of
// all array elements
int ans = 1;
// Traverse the array
for (int i = 0; i < a.Length; i++) {
ans *= a[i];
}
// Return the product
return ans;
}
// Function to find the value of X
// that satisfies the given condition
public static void findSmallestInteger(int[] A, int[] B,
int P)
{
// Stores the required smallest value
// using Chinese Remainder Theorem
int Y = findMinX(A, B, A.Length);
// Stores the product
// of all array elements
int M = product(A);
// The equation is Y + K*M >= P
// Therefore, calculate K = ceil((P-Y)/M)
int K = (int)Math.Ceiling(((double)P - (double)Y)
/ (double)M);
// So, X = Y + K*M
int X = Y + K * M;
// Print the resultant value of X
Console.WriteLine(X);
}
// Driver Code
public static void Main(string[] args)
{
int[] A = { 3, 4, 5 };
int[] B = { 2, 3, 1 };
int P = 72;
findSmallestInteger(A, B, P);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to calculate modulo
// inverse of a w.r.t m using
// Extended Euclid Algorithm
function inv(a, m)
{
var m0 = m, t, q;
var x0 = 0, x1 = 1;
// Base Case
if (m == 1)
return 0;
// Perform extended
// euclid algorithm
while (a > 1)
{
// q is quotient
q = parseInt(a / m);
t = m;
// m is remainder now,
// process same as
// euclid's algorithm
m = a % m;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
// If x1 is negative
if (x1 < 0)
// Make x1 positive
x1 += m0;
return x1;
}
// Function to implement Chinese
// Remainder Theorem to find X
function findMinX(A, B, N)
{
// Stores the product
// of array elements
var prod = 1;
// Traverse the array
for(var i = 0; i < N; i++)
// Update product
prod *= A[i];
// Initialize the result
var result = 0;
// Apply the above formula
for(var i = 0; i < N; i++)
{
var pp = parseInt(prod / A[i]);
result += B[i] * inv(pp, A[i]) * pp;
}
return result % prod;
}
// Function to calculate the product
// of all elements of the array a[]
function product(a, n)
{
// Stores product of
// all array elements
var ans = 1;
// Traverse the array
for(var i = 0; i < n; i++)
{
ans *= a[i];
}
// Return the product
return ans;
}
// Function to find the value of X
// that satisfies the given condition
function findSmallestInteger(A, B, P, n)
{
// Stores the required smallest value
// using Chinese Remainder Theorem
var Y = findMinX(A, B, n);
// Stores the product
// of all array elements
var M = product(A,n);
// The equation is Y + K*M >= P
// Therefore, calculate K = ceil((P-Y)/M)
var K = Math.ceil((P - Y) / M);
// So, X = Y + K*M
var X = Y + K * M;
// Print the resultant value of X
document.write( X);
}
// Driver Code
var A = [ 3, 4, 5 ];
var B = [ 2, 3, 1 ];
var n = A.length;
var P = 72;
findSmallestInteger(A, B, P,n);
</script>
Producción:
131
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)