Encuentre el valor de XXXX…..(N veces) % M donde N es grande

Posted on by Rudeus Greyrat

Dados tres enteros X , N y M . La tarea es encontrar XXX…(N veces) % M donde X puede ser cualquier dígito del rango [1, 9] .

Ejemplos:  

Entrada: X = 7, N = 7, M = 50 
Salida: 27 
7777777 % 50 = 27

Entrada: X = 1, N = 10, M = 9 
Salida: 1 
1111111111 % 9 = 1 
 

Enfoque: El problema se puede resolver utilizando la técnica Divide and Conquer . El módulo de números más pequeños como X, XX, XXX, etc. se puede calcular fácilmente. Pero el problema surge para números más grandes. Por lo tanto, el número se puede dividir de la siguiente manera: 

  1. Si N es par -> XXX…(N veces) = (XXX…(N/2 veces) * 10 N/2 ) + XXX..(N/2 veces).
  2. Si N es impar -> XXX…(N veces) = (XXX…(N/2 veces) * 10 (N/2)+1 ) + (XXX…(N/2 veces) * 10) + X.

Usando la fórmula anterior, el número se divide en partes más pequeñas cuya operación modular se puede encontrar fácilmente. Usando la propiedad (a + b) % m = (a % m + b % m) % m , se hace una solución recursiva de divide y vencerás para encontrar el módulo de un número más grande usando resultados de números más pequeños.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Iterative function to calculate
// (x ^ y) % p in O(log y)
int power(int x, unsigned int y, int p)
{
 
    // Initialize result
    int res = 1;
 
    // Update x if it is >= p
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        // y = y / 2
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
// Function to return XXX.....(N times) % M
int findModuloByM(int X, int N, int M)
{
 
    // Return the mod by M of smaller numbers
    if (N < 6) {
 
        // Creating a string of N X's
        string temp(N, (char)(48 + X));
 
        // Converting the string to int
        // and calculating the modulo
        int res = stoi(temp) % M;
 
        return res;
    }
 
    // Checking the parity of N
    if (N % 2 == 0) {
 
        // Dividing the number into equal half
        int half = findModuloByM(X, N / 2, M) % M;
 
        // Utilizing the formula for even N
        int res = (half * power(10, N / 2, M)
                   + half)
                  % M;
 
        return res;
    }
    else {
        // Dividing the number into equal half
        int half = findModuloByM(X, N / 2, M) % M;
 
        // Utilizing the formula for odd N
        int res = (half * power(10, N / 2 + 1, M)
                   + half * 10 + X)
                  % M;
 
        return res;
    }
}
 
// Driver code
int main()
{
    int X = 6, N = 14, M = 9;
 
    // Print XXX...(N times) % M
    cout << findModuloByM(X, N, M);
 
    return 0;
}

Java

// Java implementation of the approach
 
class GFG
{
    // Iterative function to calculate
    // (x ^ y) % p in O(log y)
    static int power(int x, int y, int p)
    {
     
        // Initialize result
        int res = 1;
     
        // Update x if it is >= p
        x = x % p;
     
        while (y > 0)
        {
     
            // If y is odd, multiply x with result
            if (y % 2 == 1)
                res = (res * x) % p;
     
            // y must be even now
            // y = y / 2
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }
     
    // Function to return XXX.....(N times) % M
    static int findModuloByM(int X, int N, int M)
    {
     
        // Return the mod by M of smaller numbers
        if (N < 6)
        {
     
            // Creating a string of N X's
            String temp="";
            for(int i = 0; i< N ; i++)
                temp = temp + (char)(X + 48);
     
            // Converting the string to int
            // and calculating the modulo
            int res = Integer.parseInt(temp) % M;
     
            return res;
        }
     
        // Checking the parity of N
        if (N % 2 == 0)
        {
     
            // Dividing the number into equal half
            int half = findModuloByM(X, N / 2, M) % M;
     
            // Utilizing the formula for even N
            int res = (half * power(10, N / 2, M)
                    + half)
                    % M;
     
            return res;
        }
        else
        {
            // Dividing the number into equal half
            int half = findModuloByM(X, N / 2, M) % M;
     
            // Utilizing the formula for odd N
            int res = (half * power(10, N / 2 + 1, M)
                    + half * 10 + X)
                    % M;
     
            return res;
        }
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int X = 6, N = 14, M = 9;
     
        // Print XXX...(N times) % M
        System.out.println(findModuloByM(X, N, M));
    }
}    
 
// This code is contributed by ihritik

Python3

# Python3 implementation of the above approach
 
# Iterative function to calculate
# (x ^ y) % p in O(log y)
def power(x, y, p) :
 
    # Initialize result
    res = 1;
 
    # Update x if it is >= p
    x = x % p;
 
    while (y > 0) :
 
        # If y is odd, multiply x with result
        if (y and 1) :
            res = (res * x) % p;
 
        # y must be even now
        # y = y // 2
        y = y >> 1;
        x = (x * x) % p;
         
    return res;
 
# Function to return XXX.....(N times) % M
def findModuloByM(X, N, M) :
 
    # Return the mod by M of smaller numbers
    if (N < 6) :
 
        # Creating a string of N X's
        temp = chr(48 + X) * N
 
        # Converting the string to int
        # and calculating the modulo
        res = int(temp) % M;
 
        return res;
 
    # Checking the parity of N
    if (N % 2 == 0) :
 
        # Dividing the number into equal half
        half = findModuloByM(X, N // 2, M) % M;
 
        # Utilizing the formula for even N
        res = (half * power(10, N // 2,
                                M) + half) % M;
 
        return res;
 
    else :
         
        # Dividing the number into equal half
        half = findModuloByM(X, N // 2, M) % M;
 
        # Utilizing the formula for odd N
        res = (half * power(10, N // 2 + 1, M) +
               half * 10 + X) % M;
 
        return res;
         
# Driver code
if __name__ == "__main__" :
 
    X = 6; N = 14; M = 9;
 
    # Print XXX...(N times) % M
    print(findModuloByM(X, N, M));
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
 
class GFG
{
    // Iterative function to calculate
    // (x ^ y) % p in O(log y)
    static int power(int x, int y, int p)
    {
     
        // Initialize result
        int res = 1;
     
        // Update x if it is >= p
        x = x % p;
     
        while (y > 0)
        {
     
            // If y is odd, multiply x with result
            if (y % 2 == 1)
                res = (res * x) % p;
     
            // y must be even now
            // y = y / 2
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }
     
    // Function to return XXX.....(N times) % M
    static int findModuloByM(int X, int N, int M)
    {
     
        // Return the mod by M of smaller numbers
        if (N < 6)
        {
     
            // Creating a string of N X's
            string temp="";
            for(int i = 0; i< N ; i++)
                temp = temp + (char)(X + 48);
     
            // Converting the string to int
            // and calculating the modulo
            int res = Convert.ToInt32(temp) % M;
     
            return res;
        }
     
        // Checking the parity of N
        if (N % 2 == 0)
        {
     
            // Dividing the number into equal half
            int half = findModuloByM(X, N / 2, M) % M;
     
            // Utilizing the formula for even N
            int res = (half * power(10, N / 2, M)
                    + half)
                    % M;
     
            return res;
        }
        else
        {
            // Dividing the number into equal half
            int half = findModuloByM(X, N / 2, M) % M;
     
            // Utilizing the formula for odd N
            int res = (half * power(10, N / 2 + 1, M)
                    + half * 10 + X)
                    % M;
     
            return res;
        }
    }
     
    // Driver code
    public static void Main ()
    {
        int X = 6, N = 14, M = 9;
     
        // Print XXX...(N times) % M
        Console.WriteLine(findModuloByM(X, N, M));
    }
}    
 
// This code is contributed by ihritik

PHP

<?php
// PHP implementation of the above approach
 
// Iterative function to calculate
// (x ^ y) % p in O(log y)
function power($x, $y, $p)
{
 
    // Initialize result
    $res = 1;
 
    // Update x if it is >= p
    $x = $x % $p;
 
    while ($y > 0)
    {
 
        // If y is odd, multiply x with result
        if ($y&1)
            $res = ($res * $x) % $p;
 
        // y must be even now
        // y = y // 2
        $y = $y >> 1;
        $x = ($x * $x) % $p;
    }
    return $res;
}
 
// Function to return XXX.....(N times) % M
function findModuloByM($X, $N, $M)
{
 
    // Return the mod by M of smaller numbers
    if ($N < 6)
    {
 
        // Creating a string of N X's
        $temp = chr(48 + $X) * $N;
 
        // Converting the string to int
        // and calculating the modulo
        $res = intval($temp) % $M;
 
        return $res;
    }
 
    // Checking the parity of N
    if ($N % 2 == 0)
    {
 
        // Dividing the number into equal half
        $half = findModuloByM($X, (int)($N / 2), $M) % $M;
 
        // Utilizing the formula for even N
        $res = ($half * power(10,(int)($N / 2),
                             $M) + $half) % $M;
 
        return $res;
    }
    else
    {
        // Dividing the number into equal half
        $half = findModuloByM($X, (int)($N / 2), $M) % $M;
 
        // Utilizing the formula for odd N
        $res = ($half * power(10, (int)($N / 2) + 1, $M) +
                $half * 10 + $X) % $M;
 
        return $res;
    }
}
 
// Driver code
$X = 6;
$N = 14;
$M = 9;
 
// Print XXX...(N times) % M
print(findModuloByM($X, $N, $M));
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript implementation of the approach
 
// Iterative function to calculate
// (x ^ y) % p in O(log y)
function power(x, y, p)
{
 
    // Initialize result
    var res = 1;
 
    // Update x if it is >= p
    x = x % p;
 
    while (y > 0)
    {
         
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        // y = y / 2
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
// Function to return XXX.....(N times) % M
function findModuloByM(X, N, M)
{
 
    // Return the mod by M of smaller numbers
    if (N < 6)
    {
        var temp = "";
         
        // Creating a string of N X's
        for(var i = 1; i < N; i++)
        {
            temp += String.fromCharCode(48 + X);
        }
 
        // Converting the string to int
        // and calculating the modulo
        var res = parseInt(temp) % M;
 
        return res;
    }
 
    // Checking the parity of N
    if (N % 2 == 0)
    {
         
        // Dividing the number into equal half
        var half = findModuloByM(X, N / 2, M) % M;
 
        // Utilizing the formula for even N
        var res = (half *
                   power(10, N / 2, M) + half) % M;
 
        return res;
    }
    else
    {
         
        // Dividing the number into equal half
        var half = findModuloByM(X, N / 2, M) % M;
 
        // Utilizing the formula for odd N
        var res = (half * power(10, N / 2 + 1, M) +
                   half * 10 + X) % M;
 
        return res;
    }
}
 
// Driver code
var X = 6, N = 14, M = 9;
 
// Print XXX...(N times) % M
document.write( findModuloByM(X, N, M));
 
// This code is contributed by noob2000
 
</script>
Producción: 

3

 

Complejidad del tiempo: O(log(N))

Complejidad espacial : O(1)

Publicación traducida automáticamente

Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *