Encuentre el primer y último M dígitos de la K-ésima potencia de N

Dados dos números enteros N y K , la tarea es encontrar el primer M y el último M dígitos del número N K .
Ejemplos: 
 

Entrada: N = 2345, K = 3, M = 3 
Salida: 128 625 
Explicación: 
2345 3 = 128 95213 625 
Por lo tanto, los primeros M(= 3) dígitos son 128 y los últimos tres dígitos son 625.
Entrada: N = 12 , K = 12, M = 4 
Salida: 8916 8256 
Explicación: 
12 12 = 8916 10044 8256 
 

Enfoque ingenuo: 
el enfoque más simple para resolver el problema es calcular el valor de N K e iterar a los primeros M dígitos y encontrar los últimos M dígitos por N K mod 10 M
Complejidad de tiempo: O(K) 
Espacio auxiliar: O(1)
Enfoque eficiente: 
El enfoque anterior se puede optimizar mediante la siguiente observación: 
 

Consideremos un número x que se puede escribir como 10 y Donde y es un número decimal. 
Sea x = N K
N K = 10 y 
Tomando log 10 en ambos lados de la expresión anterior, obtenemos: 
K * log 10 (N) = log 10 (10 y
=> K * log 10 (N) = y * (log 10 10) 
=> y = K * log 10 (N)
Ahora y será un número decimal de forma abc—.xyz— 
Por lo tanto, 
N K = 10 abc—.xyz— 
=> NK = 10 abc— + 0.xyz— 
=> N K = 10 abc— * 10 0.xyz— 
En la ecuación anterior, 10 abc— solo mueve el punto decimal hacia adelante. 
Al calcular 10 0.xyz— , los primeros M dígitos se pueden averiguar moviendo el punto decimal hacia adelante. 
 

Siga los pasos a continuación para resolver el problema: 
 

  • Encuentre los primeros M dígitos de N K calculando (N K )mod(10 M ) .
  • Calcular K * log 10 (N) .
  • Calcula 10 K * log 10 (N) .
  • Encuentre los primeros M dígitos calculando 10 K * log 10 (N) * 10 M – 1 .
  • Imprime el primer y último M dígito obtenido.

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Function to find a^b modulo M
ll modPower(ll a, ll b, ll M)
{
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return res;
}
 
// Function to find the first and last
// M digits from N^K
void findFirstAndLastM(ll N, ll K, ll M)
{
    // Calculate Last M digits
    ll lastM
        = modPower(N, K, (1LL) * pow(10, M));
 
    // Calculate First M digits
    ll firstM;
 
    double y = (double)K * log10(N * 1.0);
 
    // Extract the number after decimal
    y = y - (ll)y;
 
    // Find 10 ^ y
    double temp = pow(10.0, y);
 
    // Move the Decimal Point M - 1 digits forward
    firstM = temp * (1LL) * pow(10, M - 1);
 
    // Print the result
    cout << firstM << " " << lastM << endl;
}
 
// Driver Code
int main()
{
    ll N = 12, K = 12, M = 4;
 
    findFirstAndLastM(N, K, M);
    return 0;
}

Java

// Java program to implement
// the above approach
class GFG{
 
// Function to find a^b modulo M
static long modPower(long a, long b, long M)
{
    long res = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
            res = res * a % M;
             
        a = a * a % M;
        b >>= 1;
    }
    return res;
}
 
// Function to find the first and last
// M digits from N^K
static void findFirstAndLastM(long N, long K,
                              long M)
{
     
    // Calculate Last M digits
    long lastM = modPower(N, K, (1L) *
                 (long)Math.pow(10, M));
 
    // Calculate First M digits
    long firstM;
 
    double y = (double)K * Math.log10(N * 1.0);
 
    // Extract the number after decimal
    y = y - (long)y;
 
    // Find 10 ^ y
    double temp = Math.pow(10.0, y);
 
    // Move the Decimal Point M - 1 digits forward
    firstM = (long)(temp * (1L) *
             Math.pow(10, (M - 1)));
 
    // Print the result
    System.out.print(firstM + " " +
                      lastM + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
    long N = 12, K = 12, M = 4;
 
    findFirstAndLastM(N, K, M);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program to implement
# the above approach
from math import *
 
# Function to find a^b modulo M
def modPower(a, b, M):
 
    res = 1
    while (b):
        if (b & 1):
            res = res * a % M
             
        a = a * a % M
        b >>= 1
 
    return res
 
# Function to find the first and
# last M digits from N^K
def findFirstAndLastM(N, K, M):
 
    # Calculate Last M digits
    lastM = modPower(N, K, int(pow(10, M)))
 
    # Calculate First M digits
    firstM = 0
 
    y = K * log10(N * 1.0)
 
    # Extract the number after decimal
    y = y - int(y)
 
    # Find 10 ^ y
    temp = pow(10.0, y)
 
    # Move the Decimal Point M - 1
    # digits forward
    firstM = int(temp * pow(10, M - 1))
 
    # Print the result
    print(firstM, lastM)
 
# Driver Code
N = 12
K = 12
M = 4
 
findFirstAndLastM(N, K, M)
 
# This code is contributed by himanshu77

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find a^b modulo M
static long modPower(long a, long b, long M)
{
    long res = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
            res = res * a % M;
 
        a = a * a % M;
        b >>= 1;
    }
    return res;
}
 
// Function to find the first and last
// M digits from N^K
static void findFirstAndLastM(long N, long K,
                              long M)
{
 
    // Calculate Last M digits
    long lastM = modPower(N, K, (1L) *
                 (long)Math.Pow(10, M));
 
    // Calculate First M digits
    long firstM;
 
    double y = (double)K * Math.Log10(N * 1.0);
 
    // Extract the number after decimal
    y = y - (long)y;
 
    // Find 10 ^ y
    double temp = Math.Pow(10.0, y);
 
    // Move the Decimal Point M - 1 digits forward
    firstM = (long)(temp * (1L) *
             Math.Pow(10, (M - 1)));
 
    // Print the result
    Console.Write(firstM + " " +
                   lastM + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
    long N = 12, K = 12, M = 4;
 
    findFirstAndLastM(N, K, M);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
  
// JavaScript Program to implement
// the above approach
 
// Function to find a^b modulo M
function modPower(a, b, M)
{
    var res = 1;
    while (b) {
        if (b & 1)
            res = res * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return res;
}
 
// Function to find the first and last
// M digits from N^K
function findFirstAndLastM(N, K, M)
{
    // Calculate Last M digits
    var lastM
        = modPower(N, K, Math.pow(10, M));
 
    // Calculate First M digits
    var firstM;
 
    var y = K * Math.log10(N * 1.0);
 
    // Extract the number after decimal
    y = y - parseInt(y);
 
    // Find 10 ^ y
    var temp = Math.pow(10.0, y);
 
    // Move the Decimal Point M - 1 digits forward
    firstM = temp  * Math.pow(10, M - 1);
 
    // Print the result
    document.write( parseInt(firstM) + " "
    + parseInt(lastM) );
}
 
// Driver Code
var N = 12, K = 12, M = 4;
findFirstAndLastM(N, K, M);
 
</script>
Producción: 

8916 8256

 

Complejidad temporal: O(log K)  
Espacio auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por sri_srajit 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 *