Calcule (a*b)%c tal que (a%c) * (b%c) puede estar fuera del rango

Dados tres números a, b y c tales que a, b y c pueden ser como máximo 10 ¹⁶ . La tarea es calcular (a*b)%c 
Una solución simple de hacer ((a % c) * (b % c) ) % c no funcionaría aquí. El problema aquí es que a y b pueden ser grandes, por lo que cuando calculamos (a % c) * (b % c), va más allá del rango que puede contener long long int, por lo que se produce un desbordamiento. Por ejemplo, si a = (10 ¹² +7), b = (10 ¹³ +5), c = (10 ¹⁵ +3).
Ahora long long int puede contener hasta 4 x 10 ¹⁸ (aproximadamente) y a*b es mucho más grande que eso.
 

En lugar de hacer una multiplicación directa, podemos sumar find a + a + ……….(b veces) y tomar el módulo con c cada vez que agregamos a para que no se produzca un desbordamiento. Pero esto sería ineficiente considerando la restricción en a, b y c. De alguna manera tenemos que calcular (∑ a) % c de manera optimizada. 
Podemos usar divide y vencerás para calcularlo. La idea principal es: 
 

1. Si b es par entonces a*b = (2*a) * (b/2)
2. Si b es impar entonces a*b = a + (2*a)*((b-1)/2)

A continuación se muestra la implementación del algoritmo: 
 

// C++ program to Compute (a*b)%c
// such that (a%c) * (b%c) can be
// beyond range
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
// returns (a*b)%c
ll mulmod(ll a,ll b,ll c)
{
    // base case if b==0, return 0
    if (b==0)
        return 0;
 
    // Divide the problem into 2 parts
    ll s = mulmod(a, b/2, c);
 
    // If b is odd, return
    // (a+(2*a)*((b-1)/2))%c
    if (b%2==1)
        return (a%c+2*(s%c)) % c;
 
    // If b is odd, return
    // ((2*a)*(b/2))%c
    else
        return (2*(s%c)) % c;
}
 
// Driver code
int main()
{
    ll a = 1000000000007, b = 10000000000005;
    ll c = 1000000000000003;
    printf("%lldn", mulmod(a, b, c));
    return 0;
}

// Java program to Compute (a*b)%c
// such that (a%c) * (b%c) can be
// beyond range
// returns (a*b)%c
class GFG {
 
    static long mulmod(long a, long b, long c) {
        // base case if b==0, return 0
        if (b == 0) {
            return 0;
        }
 
        // Divide the problem into 2 parts
        long s = mulmod(a, b / 2, c);
 
        // If b is odd, return
        // (a+(2*a)*((b-1)/2))%c
        if (b % 2 == 1) {
            return (a % c + 2 * (s % c)) % c;
        } // If b is odd, return
        // ((2*a)*(b/2))%c
        else {
            return (2 * (s % c)) % c;
        }
    }
 
// Driver code
    public static void main(String[] args) {
        long a = 1000000000007L, b = 10000000000005L;
        long c = 1000000000000003L;
        System.out.println((mulmod(a, b, c)));
    }
}
 
// This code is contributed by PrinciRaj1992

# Python3 program of above approach
 
# returns (a*b)%c
def mulmod(a, b, c):
 
    # base case if b==0, return 0
    if(b == 0):
        return 0
 
    # Divide the problem into 2 parts
    s = mulmod(a, b // 2, c)
 
    # If b is odd, return
    # (a+(2*a)*((b-1)/2))%c
    if(b % 2 == 1):
        return (a % c + 2 * (s % c)) % c
 
    # If b is odd, return
    # ((2*a)*(b/2))%c
    else:
        return (2 * (s % c)) % c
 
# Driver code
if __name__=='__main__':
    a = 1000000000007
    b = 10000000000005
    c = 1000000000000003
    print(mulmod(a, b, c))
 
# This code is contributed by
# Sanjit_Prasad

// C# program to Compute (a*b)%c
// such that (a%c) * (b%c) can be
// beyond range
using System;
 
// returns (a*b)%c
class GFG
{
static long mulmod(long a, long b, long c)
{
    // base case if b==0, return 0
    if (b == 0)
        return 0;
 
    // Divide the problem into 2 parts
    long s = mulmod(a, b / 2, c);
 
    // If b is odd, return
    // (a+(2*a)*((b-1)/2))%c
    if (b % 2 == 1)
        return (a % c + 2 * (s % c)) % c;
 
    // If b is odd, return
    // ((2*a)*(b/2))%c
    else
        return (2 * (s % c)) % c;
}
 
// Driver code
public static void Main()
{
    long a = 1000000000007, b = 10000000000005;
    long c = 1000000000000003;
    Console.WriteLine(mulmod(a, b, c));
}
}
 
// This code is contributed by mits

<?php
// PHP program to Compute (a*b)%c
// such that (a%c) * (b%c) can be
// beyond range
 
// returns (a*b)%c
function mulmod($a, $b, $c)
{
     
    // base case if b==0, return 0
    if ($b==0)
        return 0;
 
    // Divide the problem into 2 parts
    $s = mulmod($a, $b/2, $c);
 
    // If b is odd, return
    // (a+(2*a)*((b-1)/2))%c
    if ($b % 2 == 1)
        return ($a % $c + 2 *
           ($s % $c))  %  $c;
 
    // If b is odd, return
    // ((2*a)*(b/2))%c
    else
        return (2 * ($s % $c)) % $c;
}
 
    // Driver Code
    $a = 1000000000007;
    $b = 10000000000005;
    $c = 1000000000000003;
    echo mulmod($a, $b, $c);
     
// This code is contributed by anuj_67.
?>

<script>
 
// javascript program to Compute (a*b)%c
// such that (a%c) * (b%c) can be
// beyond range
// returns (a*b)%c  
function mulmod(a , b , c) {
 
        // base case if b==0, return 0
        if (b == 0) {
            return 0;
        }
 
        // Divide the problem into 2 parts
        var s = mulmod(a, parseInt(b / 2), c);
 
        // If b is odd, return
        // (a+(2*a)*((b-1)/2))%c
        if (b % 2 == 1) {
            return (a % c + 2 * (s % c)) % c;
        }
        // If b is odd, return
        // ((2*a)*(b/2))%c
        else {
            return (2 * (s % c)) % c;
        }
    }
 
// Driver code
var a = 1000000000007, b = 10000000000005;
var c = 1000000000000003;
document.write((mulmod(a, b, c)));
 
// This code contributed by Princi Singh
 
</script>

Producción : 

74970000000035

Vea esto para una ejecución de muestra.
Complejidad de tiempo: O(log b)
Este artículo es una contribución de Madhur Modi . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.