Рубрики

Умножьте большие целые числа на большие по модулю

Математика

Дано целое число a, b, m. Найдите (a * b) mod m, где a, b могут быть большими, и их прямое умножение может вызвать переполнение. Однако они меньше половины максимально допустимого значения long long int.

Примеры:

Input: a = 426, b = 964, m = 235
Output: 119
Explanation: (426 * 964) % 235  
            = 410664 % 235
            = 119

Input: a = 10123465234878998, 
       b = 65746311545646431
       m = 10005412336548794 
Output: 4652135769797794

Наивный подход состоит в том, чтобы использовать тип данных произвольной точности, такой как int в python или класс Biginteger в Java. Но такой подход не будет плодотворным, поскольку внутреннее преобразование строки в int и последующая операция приведут к замедлению вычислений сложения и умножения в двоичной системе счисления.

Эффективное решение: так как a и b могут быть очень большими числами, если мы попытаемся умножить непосредственно, тогда это определенно переполнится. Поэтому мы используем базовый подход умножения, т. Е.

a * b = a + a +… + a (b раз)
Таким образом, мы можем легко вычислить значение сложения (по модулю m) без каких-либо
переполнение в расчете. Но если мы попытаемся добавить значение a многократно до b раз, то это определенно приведет к превышению времени ожидания для большого значения b, поскольку временная сложность этого подхода станет O (b).

Таким образом, мы делим вышеупомянутые повторные шаги более простым способом, т.е.

If b is even then 
  a * b = 2 * a * (b / 2), 
otherwise 
  a * b = a + a * (b - 1)

Ниже представлен подход, описывающий приведенное выше объяснение:

C ++

// C ++ программа нахождения умножения по модулю
#include<bits/stdc++.h>

  

using namespace std;

  
// Возвращает (a * b)% mod

long long moduloMultiplication(long long a,

                            long long b,

                            long long mod)

{

    long long res = 0; // Инициализировать результат

  

    // Обновление, если оно больше

    // или равно моду

    a %= mod;

  

    while (b)

    {

        // Если b нечетно, добавить a с результатом

        if (b & 1)

            res = (res + a) % mod;

  

        // Здесь мы предполагаем, что делаем 2 * a

        // не вызывает переполнения

        a = (2 * a) % mod;

  

        b >>= 1; // b = b / 2

    }

  

    return res;

}

  
// Драйвер программы

int main()

{

    long long a = 10123465234878998;

    long long b = 65746311545646431;

    long long m = 10005412336548794;

    cout << moduloMultiplication(a, b, m);

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

// C программа нахождения умножения по модулю
#include<stdio.h>

  
// Возвращает (a * b)% mod

long long moduloMultiplication(long long a,

                               long long b,

                               long long mod)

{

    long long res = 0;  // Инициализировать результат

  

    // Обновление, если оно больше

    // или равно моду

    a %= mod;

  

    while (b)

    {

        // Если b нечетно, добавить a с результатом

        if (b & 1)

            res = (res + a) % mod;

  

        // Здесь мы предполагаем, что делаем 2 * a

        // не вызывает переполнения

        a = (2 * a) % mod;

  

        b >>= 1;  // b = b / 2

    }

  

    return res;

}

  
// Драйвер программы

int main()

{

    long long a = 10123465234878998;

    long long b = 65746311545646431;

    long long m = 10005412336548794;

    printf("%lld", moduloMultiplication(a, b, m));

    return 0;

}

Джава

// Java программа нахождения умножения по модулю

class GFG 

{

  

    // Возвращает (a * b)% mod

    static long moduloMultiplication(long a,

                            long b, long mod)

    {

          

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

        long res = 0;  

  

        // Обновление, если оно больше

        // или равно моду

        a %= mod;

  

        while (b > 0) 

        {

              

            // Если b нечетно, добавить a с результатом

            if ((b & 1) > 0) 

            {

                res = (res + a) % mod;

            }

  

            // Здесь мы предполагаем, что делаем 2 * a

            // не вызывает переполнения

            a = (2 * a) % mod;

  

            b >>= 1; // b = b / 2

        }

        return res;

    }

  

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

    public static void main(String[] args) 

    {

        long a = 10123465234878998L;

        long b = 65746311545646431L;

        long m = 10005412336548794L;

        System.out.print(moduloMultiplication(a, b, m));

    }

} 

  
// Этот код предоставлен Rajput-JI

Python 3

# Python 3 программа поиска
# умножение по модулю

  
# Возвращает (a * b)% mod

def moduloMultiplication(a, b, mod):

  

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

  

    # Обновите, если оно больше чем

    # или равно мод

    a = a % mod;

  

    while (b):

      

        # Если b нечетно, добавить с результатом

        if (b & 1):

            res = (res + a) % mod;

              

        # Здесь мы предполагаем, что делать 2 *

        # не вызывает переполнения

        a = (2 * a) % mod;

  

        b >>= 1; # b = b / 2

      

    return res;

  
Код водителя

a = 10123465234878998;

b = 65746311545646431;

m = 10005412336548794;

print(moduloMultiplication(a, b, m));

      
# Этот код добавлен
# by Shivi_Aggarwal

C #

// C # программа нахождения умножения по модулю

using System;

  

class GFG

{

      
// Возвращает (a * b)% mod

static long moduloMultiplication(long a,

                            long b,

                            long mod)

{

    long res = 0; // Инициализировать результат

  

    // Обновление, если оно больше

    // или равно моду

    a %= mod;

  

    while (b > 0)

    {

        // Если b нечетно, добавить a с результатом

        if ((b & 1) > 0)

            res = (res + a) % mod;

  

        // Здесь мы предполагаем, что делаем 2 * a

        // не вызывает переполнения

        a = (2 * a) % mod;

  

        b >>= 1; // b = b / 2

    }

  

    return res;

}

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

static void Main()

{

    long a = 10123465234878998;

    long b = 65746311545646431;

    long m = 10005412336548794;

    Console.WriteLine(moduloMultiplication(a, b, m));

}
}

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

PHP

<?php
// PHP программа поиска
// умножение по модулю

  
// Возвращает (a * b)% mod

function moduloMultiplication($a, $b, $mod)

{

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

  

    // Обновление, если оно больше

    // или равно моду

    $a %= $mod;

  

    while ($b)

    {

          

        // Если b нечетно,

        // добавить результат

        if ($b & 1)

            $res = ($res + $a) % $mod;

  

        // Здесь мы предполагаем, что делаем 2 * a

        // не вызывает переполнения

        $a = (2 * $a) % $mod;

  

        $b >>= 1; // b = b / 2

    }

  

    return $res;

}

  

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

    $a = 10123465234878998;

    $b = 65746311545646431;

    $m = 10005412336548794;

    echo moduloMultiplication($a, $b, $m);

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


Выход:

4652135769797794

Временная сложность: O (log b)
Вспомогательное пространство: O (1)

Примечание. Приведенный выше подход будет работать только в том случае, если 2 * m можно представить в стандартном типе данных, в противном случае это приведет к переполнению.

Эта статья предоставлена Shubham Bansal . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Умножьте большие целые числа на большие по модулю

0.00 (0%) 0 votes