Рубрики

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

Нам даны два массива 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] 

Пример:

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. 

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

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

Мы обсудили наивное решение, чтобы найти минимум х. В этой статье обсуждается эффективное решение для поиска х.

Решение основано на формуле ниже.


x =  ( ∑ (rem[i]*pp[i]*inv[i]) ) % prod
   Where 0 <= i <= n-1

rem[i] is given array of remainders

prod is product of all given numbers
prod = num[0] * num[1] * ... * num[k-1]

pp[i] is product of all divided by num[i]
pp[i] = prod / num[i]

inv[i] = Modular Multiplicative Inverse of 
         pp[i] with respect to num[i]

Пример:

Let us take below example to understand the solution
   num[] = {3, 4, 5}, rem[] = {2, 3, 1}
   prod  = 60 
   pp[]  = {20, 15, 12}
   inv[] = {2,  3,  3}  // (20*2)%3 = 1, (15*3)%4 = 1
                        // (12*3)%5 = 1

   x = (rem[0]*pp[0]*inv[0] + rem[1]*pp[1]*inv[1] + 
        rem[2]*pp[2]*inv[2]) % prod
     = (2*20*2 + 3*15*3 + 1*12*3) % 60
     = (40 + 135 + 36) % 60
     = 11

Обратитесь к этому для хорошего визуального объяснения вышеприведенной формулы.

Ниже приведена реализация приведенной выше формулы. Мы можем использовать метод, основанный на расширенном Евклиде, обсуждаемый здесь, чтобы найти обратное по модулю.

C ++

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

using namespace std;

  
// Возвращает по модулю инверсию a относительно m, используя расширенный
// Алгоритм Евклида. Смотрите ниже пост для деталей:
// https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/amp/

int inv(int a, int m)

{

    int m0 = m, t, q;

    int x0 = 0, x1 = 1;

  

    if (m == 1)

       return 0;

  

    // Применяем расширенный алгоритм Евклида

    while (a > 1)

    {

        // q является частным

        q = a / m;

  

        t = m;

  

        // m теперь остаток, процесс такой же как

        // Алгоритм Евклида

        m = a % m, a = t;

  

        t = x0;

  

        x0 = x1 - q * x0;

  

        x1 = t;

    }

  

    // Сделать x1 положительным

    if (x1 < 0)

       x1 += m0;

  

    return x1;

}

  
// 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 prod = 1;

    for (int i = 0; i < k; i++)

        prod *= num[i];

  

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

    int result = 0;

  

    // Применить приведенную выше формулу

    for (int i = 0; i < k; i++)

    {

        int pp = prod / num[i];

        result += rem[i] * inv(pp, num[i]) * pp;

    }

  

    return result % prod;

}

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

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

import java.io.*;

  

class GFG {

      

    // Возвращает по модулю инверсию

    // относительно m используя расширенный

    // Алгоритм Евклида. Смотрите ниже пост для деталей:

    // https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/amp/

    static int inv(int a, int m)

    {

        int m0 = m, t, q;

        int x0 = 0, x1 = 1;

      

        if (m == 1)

        return 0;

      

        // Применяем расширенный алгоритм Евклида

        while (a > 1)

        {

            // q является частным

            q = a / m;

      

            t = m;

      

            // m осталось, процесс

            // То же, что и алгоритм Евклида

            m = a % m;a = t;

      

            t = x0;

      

            x0 = x1 - q * x0;

      

            x1 = t;

        }

      

        // Сделать x1 положительным

        if (x1 < 0)

        x1 += m0;

      

        return x1;

    }

      

    // 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 prod = 1;

        for (int i = 0; i < k; i++)

            prod *= num[i];

      

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

        int result = 0;

      

        // Применить приведенную выше формулу

        for (int i = 0; i < k; i++)

        {

            int pp = prod / num[i];

            result += rem[i] * inv(pp, num[i]) * pp;

        }

      

        return result % prod;

    }

      

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

    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

# Программа Python 3 для демонстрации
# рабочий остаток Китая
# Теорема

  
# Возвращает по модулю инверсию с
# уважение к м, используя расширенный
Алгоритм Евклида. См ниже
# пост для подробностей:
# https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/amp/

def inv(a, m) :

      

    m0 = m

    x0 = 0

    x1 = 1

  

    if (m == 1) :

        return 0

  

    # Применить расширенный алгоритм Евклида

    while (a > 1) :

        # q является частным

        q = a // m

  

        t = m

  

        # m осталось, процесс

        # так же, как алгоритм Евклида

        m = a % m

        a = t

  

        t = x0

  

        x0 = x1 - q * x0

  

        x1 = t

      

    # Сделайте x1 положительным

    if (x1 < 0) :

        x1 = x1 + m0

  

    return x1

  
# k - это размер num [] и rem [].
# Возвращает наименьшее
# число х такое, что:
# 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) :

      

    # Вычислить произведение всех чисел

    prod = 1

    for i in range(0, k) :

        prod = prod * num[i]

  

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

    result = 0

  

    # Примените приведенную выше формулу

    for i in range(0,k):

        pp = prod // num[i]

        result = result + rem[i] * inv(pp, num[i]) * pp

      

      

    return result % prod

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

num = [3, 4, 5]

rem = [2, 3, 1]

k = len(num)

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

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

C #

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

using System;

  

class GFG

{

    // Возвращает по модулю инверсию

    // 'a' относительно 'm'

    // используя расширенный алгоритм Евклида.

    // Подробнее смотрите ниже

    // https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/amp/

    static int inv(int a, int m)

    {

        int m0 = m, t, q;

        int x0 = 0, x1 = 1;

      

        if (m == 1)

        return 0;

      

        // Применить расширенный

        // Алгоритм Евклида

        while (a > 1)

        {

            // q является частным

            q = a / m;

      

            t = m;

      

            // теперь остаток

            // обрабатывать так же, как

            // Алгоритм Евклида

            m = a % m; a = t;

      

            t = x0;

      

            x0 = x1 - q * x0;

      

            x1 = t;

        }

      

        // Сделать x1 положительным

        if (x1 < 0)

        x1 += m0;

      

        return x1;

    }

      

    // 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 prod = 1;

        for (int i = 0; i < k; i++)

            prod *= num[i];

      

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

        int result = 0;

      

        // Применить приведенную выше формулу

        for (int i = 0; i < k; i++)

        {

            int pp = prod / num[i];

            result += rem[i] * 

                      inv(pp, num[i]) * pp;

        }

      

        return result % prod;

    }

      

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

    static public void Main ()

    {

        int []num = {3, 4, 5};

        int []rem = {2, 3, 1};

        int k = num.Length;

        Console.WriteLine("x is "

                          findMinX(num, rem, k));

    }

}

  
// Этот код добавлен
// от ajit

PHP

<?php
// PHP программа для демонстрации работы
// китайской теоремы об остатке

  
// Возвращает по модулю инверсию с
// уважение к м с использованием расширенного Евклида
// Алгоритм. Смотрите ниже пост для деталей:
// https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/amp/

function inv($a, $m)

{

    $m0 = $m;

    $x0 = 0;

    $x1 = 1;

  

    if ($m == 1)

    return 0;

  

    // Применяем расширенный алгоритм Евклида

    while ($a > 1)

    {

        // q является частным

        $q = (int)($a / $m);

  

        $t = $m;

  

        // m осталось, процесс

        // То же, что и алгоритм Евклида

        $m = $a % $m;

        $a = $t;

  

        $t = $x0;

  

        $x0 = $x1 - $q * $x0;

  

        $x1 = $t;

    }

  

    // Сделать x1 положительным

    if ($x1 < 0)

    $x1 += $m0;

  

    return $x1;

}

  
// k - это размер num [] и rem [].
// Возвращает наименьшее
// число х такое, что:
// 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)

{

    // Вычисляем произведение всех чисел

    $prod = 1;

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

        $prod *= $num[$i];

  

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

    $result = 0;

  

    // Применить приведенную выше формулу

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

    {

        $pp = (int)$prod / $num[$i];

        $result += $rem[$i] * inv($pp,

                      $num[$i]) * $pp;

    }

  

    return $result % $prod;

}

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

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

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

$k = sizeof($num);

echo "x is ". findMinX($num, $rem, $k);

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


Выход:

x is 11

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

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

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

0.00 (0%) 0 votes