Рубрики

Китайская теорема об остатках | Комплект 1 (Введение)

Нам даны два массива num [0..k-1] и rem [0..k-1]. В num [0..k-1] каждая пара взаимно проста (для каждой пары gcd равен 1). Нам нужно найти минимальное положительное число x такое, что:

     x % num[0]    =  rem[0], 
     x % num[1]    =  rem[1], 
     .......................
     x % num[k-1]  =  rem[k-1] 

По сути, нам дано k чисел, которые попарно взаимно просты, и даны остатки этих чисел, когда неизвестное число x делится на них. Нам нужно найти минимально возможное значение х, которое дает данные остатки.

Примеры :

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.

Теорема об оставшемся китае утверждает, что всегда существует x, удовлетворяющий данным конгруэнциям. Ниже приведено утверждение теоремы, адаптированное из Википедии .

Пусть num [0], num [1],… num [k-1] являются натуральными числами, попарно взаимно простыми. Тогда для любой данной последовательности целых чисел rem [0], rem [1],… rem [k-1] существует целое число x, решающее следующую систему одновременных сравнений.

Первая часть ясно, что существует х. Вторая часть в основном утверждает, что все решения (включая минимальное) производят одинаковый остаток при делении на произведение n [0], num [1], .. num [k-1]. В приведенном выше примере продукт равен 3 * 4 * 5 = 60. И 11 — это одно решение, другие решения — это 71, 131 и т. Д. Все эти решения дают одинаковый остаток при делении на 60, т. Е. Они имеют форму 11 + m * 60, где m> = 0.

Наивный подход, чтобы найти x, состоит в том, чтобы начать с 1 и постепенно увеличивать его и проверять, дает ли разделение на заданные элементы в num [] соответствующие остатки в rem []. Как только мы найдем такой топор, мы его вернем.

Ниже приведена реализация Наивного подхода.

C ++

// Программа на C ++, демонстрирующая работу остатка Chinise
// Теорема
#include<bits/stdc++.h>

using namespace std;

  
// k - это размер num [] и rem []. Возвращает самое маленькое
// число х такое, что:
// x% num [0] = rem [0],
// x% num [1] = rem [1],
// ..................
// x% num [k-2] = rem [k-1]
// Предположение: числа в num [] попарно взаимно просты
// (gcd для каждой пары равен 1)

int findMinX(int num[], int rem[], int k)

{

    int x = 1; // Инициализировать результат

  

    // Согласно теореме об остатках Чиниза,

    // этот цикл всегда будет прерываться

    while (true)

    {

        // Проверяем, является ли остаток от x% num [j]

        // rem [j] или нет (для всех j от 0 до k-1)

        int j;

        for (j=0; j<k; j++ )

            if (x%num[j] != rem[j])

               break;

  

        // Если все остатки совпадают, мы нашли х

        if (j == k)

            return x;

  

        // иначе попробуй следующий номер

        x++;

    }

  

    return x;

}

  
// Метод драйвера

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-программа для демонстрации работы остатка Chinise
// Теорема

import java.io.*;

  

class GFG {

      

    // k - это размер num [] и rem []. Возвращает самое маленькое

    // число х такое, что:

    // x% num [0] = rem [0],

    // x% num [1] = rem [1],

    // ..................

    // x% num [k-2] = rem [k-1]

    // Предположение: числа в num [] попарно взаимно просты

    // (gcd для каждой пары равен 1)

    static int findMinX(int num[], int rem[], int k)

    {

        int x = 1; // Инициализировать результат

       

        // Согласно теореме об остатках Чиниза,

        // этот цикл всегда будет прерываться

        while (true)

        {

            // Проверяем, является ли остаток от x% num [j]

            // rem [j] или нет (для всех j от 0 до k-1)

            int j;

            for (j=0; j<k; j++ )

                if (x%num[j] != rem[j])

                   break;

       

            // Если все остатки совпадают, мы нашли х

            if (j == k)

                return x;

       

            // иначе попробуй следующий номер

            x++;

        }

       

    }

       

    // Метод драйвера

    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));

    }

}

  
/ * Этот код предоставлен Никитой Тивари. * /

python3

# Программа Python3 для демонстрации
# обработка китайской теоремы об остатке

  
# k - это размер num [] и rem [].
# Возвращает наименьшее число x
# такое что:
# x% num [0] = rem [0],
# x% num [1] = rem [1],
# ..................
# x% num [k-2] = rem [k-1]
# Предположение: числа в num []
# попарно взаимно просты (gcd для
# каждая пара 1)

def findMinX(num, rem, k):

    x = 1; # Инициализировать результат

  

    # Согласно китайскому остатку

    # Теорема, этот цикл будет

    # всегда ломайся

    while(True):

          

        # Проверьте, если остаток

        # x% num [j] является rem [j]

        # или нет (для всех j из

        № 0 к к-1)

        j = 0;

        while(j < k):

            if (x % num[j] != rem[j]):

                break;

            j += 1;

  

        # Если все остатки

        # совпало, мы нашли х

        if (j == k):

            return x;

  

        # Еще попробуйте следующий номер

        x += 1;

  
Код водителя

num = [3, 4, 5];

rem = [2, 3, 1];

k = len(num);

print("x is", findMinX(num, rem, k));

  
# Этот код предоставлен mits

C #

// C # программа для демонстрации работы
// китайской теоремы об остатке

using System;

  

class GFG

{

      

    // k - это размер num [] и rem [].

    // Возвращает наименьшее

    // число х такое, что:

    // x% num [0] = rem [0],

    // x% num [1] = rem [1],

    // ..................

    // x% num [k-2] = rem [k-1]

    // Предположение: числа в num []

    // попарно взаимно просты

    // (gcd для каждой пары равен 1)

    static int findMinX(int []num, int []rem,

                        int k)

    {

          

        // Инициализировать результат

        int x = 1; 

      

        // Согласно теореме об остатках Чиниза,

        // этот цикл всегда будет прерываться

        while (true)

        {

            // Проверяем, является ли остаток от x% num [j]

            // rem [j] или нет (для всех j от 0 до k-1)

            int j;

            for (j = 0; j < k; j++ )

                if (x % num[j] != rem[j])

                break;

      

            // Если все остатки совпадают, мы нашли х

            if (j == k)

                return x;

      

            // иначе попробуй следующий номер

            x++;

        }

      

    }

      

    // Код драйвера

    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));

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP-программа для демонстрации
// рабочая теорема об остатке по Китаю

  
// k - это размер num [] и rem [].
// Возвращает наименьшее число x
// такой, что:
// x% num [0] = rem [0],
// x% num [1] = rem [1],
// ..................
// x% num [k-2] = rem [k-1]
// Предположение: числа в num []
// попарно взаимно просты (gcd для
// каждая пара 1)

function findMinX($num, $rem, $k)

{

    $x = 1; // Инициализировать результат

  

    // Согласно китайскому остатку

    // Теорема, этот цикл будет

    // всегда ломаемся

    while (true)

    {

        // Проверяем остаток

        // x% num [j] является rem [j]

        // или нет (для всех j из

        // от 0 до k-1)

        $j;

        for ($j = 0; $j < $k; $j++ )

            if ($x % $num[$j] != $rem[$j])

            break;

  

        // Если все остатки

        // совпало, мы нашли х

        if ($j == $k)

            return $x;

  

        // иначе попробуй следующий номер

        $x++;

    }

  

    return $x;

}

  
// Код драйвера

$num = array(3, 4, 5);

$rem = array(2, 3, 1);

$k = sizeof($num);

echo "x is "

    findMinX($num, $rem, $k);

  
// Этот код предоставлен ajit
?>

Выход :

x is 11

Смотрите ссылку ниже для эффективного метода, чтобы найти х.

Китайская теорема об остатках | Набор 2 (обратная реализация по модулю)

Эта статья предоставлена Ruchir Garg . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Китайская теорема об остатках | Комплект 1 (Введение)

0.00 (0%) 0 votes