Nos dan dos arrays num[0..k-1] y rem[0..k-1]. En num[0..k-1], cada par es coprimo (mcd para cada par es 1). Necesitamos encontrar el número positivo mínimo x tal que:
x % num[0] = rem[0],
x % num[1] = rem[1],
.......................
x % num[k-1] = rem[k-1]
Básicamente, nos dan k números que son coprimos por pares, y nos dan los restos de estos números cuando un número desconocido x se divide por ellos. Necesitamos encontrar el valor mínimo posible de x que produce residuos dados.
Ejemplos:
Input: num[] = {5, 7}, rem[] = {1, 3}
Output: 31
Explanation:
31 is the smallest number such that:
(1) When we divide it by 5, we get remainder 1.
(2) When we divide it by 7, we get remainder 3.
Input: num[] = {3, 4, 5}, rem[] = {2, 3, 1}
Output: 11
Explanation:
11 is the smallest number such that:
(1) When we divide it by 3, we get remainder 2.
(2) When we divide it by 4, we get remainder 3.
(3) When we divide it by 5, we get remainder 1.
El teorema chino del resto establece que siempre existe una x que satisface las congruencias dadas. A continuación se muestra la declaración del teorema adaptada de wikipedia .
Sean num[0], num[1], …num[k-1] números enteros positivos que son coprimos por pares. Entonces, para cualquier secuencia dada de enteros rem[0], rem[1], … rem[k-1], existe un entero x que resuelve el siguiente sistema de congruencias simultáneas.
La primera parte es clara que existe una x. La segunda parte básicamente establece que todas las soluciones (incluida la mínima) producen el mismo resto cuando se dividen por n[0], num[1], .. num[k-1]. En el ejemplo anterior, el producto es 3*4*5 = 60. Y 11 es una solución, otras soluciones son 71, 131, .. etc. Todas estas soluciones dan el mismo resto al dividirlas por 60, es decir, son de forma 11 + m*60 donde m >= 0.
Un enfoque ingenuo para encontrar x es comenzar con 1 e incrementarlo uno por uno y verificar si dividirlo con los elementos dados en num[] produce los residuos correspondientes en rem[]. Una vez que encontramos tal x, la devolvemos.
A continuación se muestra la implementación del enfoque ingenuo.
C++
// A C++ program to demonstrate working of Chinise remainder
// Theorem
#include<bits/stdc++.h>
using namespace std;
// k is size of num[] and rem[]. Returns the smallest
// number x such that:
// x % num[0] = rem[0],
// x % num[1] = rem[1],
// ..................
// x % num[k-2] = rem[k-1]
// Assumption: Numbers in num[] are pairwise coprime
// (gcd for every pair is 1)
int findMinX(int num[], int rem[], int k)
{
int x = 1; // Initialize result
// As per the Chinese remainder theorem,
// this loop will always break.
while (true)
{
// Check if remainder of x % num[j] is
// rem[j] or not (for all j from 0 to k-1)
int j;
for (j=0; j<k; j++ )
if (x%num[j] != rem[j])
break;
// If all remainders matched, we found x
if (j == k)
return x;
// Else try next number
x++;
}
return x;
}
// Driver method
int main(void)
{
int num[] = {3, 4, 5};
int rem[] = {2, 3, 1};
int k = sizeof(num)/sizeof(num[0]);
cout << "x is " << findMinX(num, rem, k);
return 0;
}
Java
// A Java program to demonstrate the working of Chinese remainder
// Theorem
import java.io.*;
class GFG {
// k is size of num[] and rem[]. Returns the smallest
// number x such that:
// x % num[0] = rem[0],
// x % num[1] = rem[1],
// ..................
// x % num[k-2] = rem[k-1]
// Assumption: Numbers in num[] are pairwise coprime
// (gcd for every pair is 1)
static int findMinX(int num[], int rem[], int k)
{
int x = 1; // Initialize result
// As per the Chinese remainder theorem,
// this loop will always break.
while (true)
{
// Check if remainder of x % num[j] is
// rem[j] or not (for all j from 0 to k-1)
int j;
for (j=0; j<k; j++ )
if (x%num[j] != rem[j])
break;
// If all remainders matched, we found x
if (j == k)
return x;
// Else try next number
x++;
}
}
// Driver method
public static void main(String args[])
{
int num[] = {3, 4, 5};
int rem[] = {2, 3, 1};
int k = num.length;
System.out.println("x is " + findMinX(num, rem, k));
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# A Python3 program to demonstrate
# working of Chinise remainder Theorem
# k is size of num[] and rem[].
# Returns the smallest number x
# such that:
# x % num[0] = rem[0],
# x % num[1] = rem[1],
# ..................
# x % num[k-2] = rem[k-1]
# Assumption: Numbers in num[]
# are pairwise coprime (gcd for
# every pair is 1)
def findMinX(num, rem, k):
x = 1; # Initialize result
# As per the Chinise remainder
# theorem, this loop will
# always break.
while(True):
# Check if remainder of
# x % num[j] is rem[j]
# or not (for all j from
# 0 to k-1)
j = 0;
while(j < k):
if (x % num[j] != rem[j]):
break;
j += 1;
# If all remainders
# matched, we found x
if (j == k):
return x;
# Else try next number
x += 1;
# Driver Code
num = [3, 4, 5];
rem = [2, 3, 1];
k = len(num);
print("x is", findMinX(num, rem, k));
# This code is contributed by mits
C#
// C# program to demonstrate working
// of Chinise remainder Theorem
using System;
class GFG
{
// k is size of num[] and rem[].
// Returns the smallest
// number x such that:
// x % num[0] = rem[0],
// x % num[1] = rem[1],
// ..................
// x % num[k-2] = rem[k-1]
// Assumption: Numbers in num[]
// are pairwise coprime
// (gcd for every pair is 1)
static int findMinX(int []num, int []rem,
int k)
{
// Initialize result
int x = 1;
// As per the Chinese remainder theorem,
// this loop will always break.
while (true)
{
// Check if remainder of x % num[j] is
// rem[j] or not (for all j from 0 to k-1)
int j;
for (j = 0; j < k; j++ )
if (x % num[j] != rem[j])
break;
// If all remainders matched, we found x
if (j == k)
return x;
// Else try next number
x++;
}
}
// Driver code
public static void Main()
{
int []num = {3, 4, 5};
int []rem = {2, 3, 1};
int k = num.Length;
Console.WriteLine("x is " + findMinX(num,
rem, k));
}
}
// This code is contributed by Sam007.
PHP
<?php
// A PHP program to demonstrate
// working of Chinise remainder Theorem
// k is size of num[] and rem[].
// Returns the smallest number x
// such that:
// x % num[0] = rem[0],
// x % num[1] = rem[1],
// ..................
// x % num[k-2] = rem[k-1]
// Assumption: Numbers in num[]
// are pairwise coprime (gcd for
// every pair is 1)
function findMinX($num, $rem, $k)
{
$x = 1; // Initialize result
// As per the Chinise remainder
// theorem, this loop will
// always break.
while (true)
{
// Check if remainder of
// x % num[j] is rem[j]
// or not (for all j from
// 0 to k-1)
$j;
for ($j = 0; $j < $k; $j++ )
if ($x % $num[$j] != $rem[$j])
break;
// If all remainders
// matched, we found x
if ($j == $k)
return $x;
// Else try next number
$x++;
}
return $x;
}
// Driver Code
$num = array(3, 4, 5);
$rem = array(2, 3, 1);
$k = sizeof($num);
echo "x is " ,
findMinX($num, $rem, $k);
// This code is contributed by ajit
?>
Javascript
<script>
// A javascript program to demonstrate the working of Chinese remainder
// Theorem
// k is size of num and rem. Returns the smallest
// number x such that:
// x % num[0] = rem[0],
// x % num[1] = rem[1],
// ..................
// x % num[k-2] = rem[k-1]
// Assumption: Numbers in num are pairwise coprime
// (gcd for every pair is 1)
function findMinX(num , rem , k)
{
var x = 1; // Initialize result
// As per the Chinese remainder theorem,
// this loop will always break.
while (true)
{
// Check if remainder of x % num[j] is
// rem[j] or not (for all j from 0 to k-1)
var j;
for (j=0; j<k; j++ )
if (x%num[j] != rem[j])
break;
// If all remainders matched, we found x
if (j == k)
return x;
// Else try next number
x++;
}
}
// Driver method
var num = [3, 4, 5];
var rem = [2, 3, 1];
var k = num.length;
document.write("x is " + findMinX(num, rem, k));
// This code is contributed by 29AjayKumar
</script>
Producción :
x is 11
Complejidad de tiempo: O(M), M es el producto de todos los elementos de la array num[].
Espacio Auxiliar : O(1)
Consulte el enlace a continuación para obtener un método eficiente para encontrar x.
Teorema chino del resto | Conjunto 2 (Implementación basada en módulo inverso) Ruchir Garg
contribuye con este artículo . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA