Te dan dos números enteros, la base a (número de dígitos d, tal que 1 <= d <= 1000) y el índice b (0 <= b <= 922*10^15). Tienes que encontrar el último dígito de a^b.
Ejemplos:
Input : 3 10 Output : 9 Input : 6 2 Output : 6 Input : 150 53 Output : 0
Después de tomar algunos ejemplos, podemos notar el siguiente patrón.
Number | Last digits that repeat in cycle 1 | 1 2 | 4, 8, 6, 2 3 | 9, 7, 1, 3 4 | 6, 4 5 | 5 6 | 6 7 | 9, 3, 1, 7 8 | 4, 2, 6, 8 9 | 1, 9
En la tabla dada, podemos ver que la longitud máxima para la repetición del ciclo es 4.
Ejemplo: 2*2 = 4*2 = 8*2 = 16*2 = 32 el último dígito en 32 es 2, lo que significa que después de multiplicar 4 veces el dígito se repite sí mismo. Así que el algoritmo es muy simple.
Fuente: Brilliants.org
Algoritmo:
- Dado que el número es muy grande, los almacenamos como una string.
- Toma el último dígito en la base a.
- Ahora calcula b%4. Aquí b es muy grande.
- Si b%4==0, eso significa que b es completamente divisible por 4, entonces nuestro exponente ahora será exp = 4 porque al multiplicar el número 4 veces, obtenemos el último dígito de acuerdo con la tabla de ciclos en el diagrama anterior.
- Si b%4!=0, eso significa que b no es completamente divisible por 4, entonces nuestro exponente ahora será exp=b%4 porque al multiplicar el exponente numérico por el número, obtenemos el último dígito de acuerdo con la tabla de ciclos en el diagrama anterior.
- Ahora calcule ldigit = pow( last_digit_in_base, exp ).
- El último dígito de a^b será ldigit%10.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ code to find last digit of a^b
#include <bits/stdc++.h>
using namespace std;
// Function to find b % a
int Modulo(int a, char b[])
{
// Initialize result
int mod = 0;
// calculating mod of b with a to make
// b like 0 <= b < a
for (int i = 0; i < strlen(b); i++)
mod = (mod * 10 + b[i] - '0') % a;
return mod; // return modulo
}
// function to find last digit of a^b
int LastDigit(char a[], char b[])
{
int len_a = strlen(a), len_b = strlen(b);
// if a and b both are 0
if (len_a == 1 && len_b == 1 && b[0] == '0' && a[0] == '0')
return 1;
// if exponent is 0
if (len_b == 1 && b[0] == '0')
return 1;
// if base is 0
if (len_a == 1 && a[0] == '0')
return 0;
// if exponent is divisible by 4 that means last
// digit will be pow(a, 4) % 10.
// if exponent is not divisible by 4 that means last
// digit will be pow(a, b%4) % 10
int exp = (Modulo(4, b) == 0) ? 4 : Modulo(4, b);
// Find last digit in 'a' and compute its exponent
int res = pow(a[len_a - 1] - '0', exp);
// Return last digit of result
return res % 10;
}
// Driver program to run test case
int main()
{
char a[] = "117", b[] = "3";
cout << LastDigit(a, b);
return 0;
}
Java
// Java code to find last digit of a^b
import java.io.*;
import java.math.*;
class GFG {
// Function to find b % a
static int Modulo(int a, char b[])
{
// Initialize result
int mod = 0;
// calculating mod of b with a to make
// b like 0 <= b < a
for (int i = 0; i < b.length; i++)
mod = (mod * 10 + b[i] - '0') % a;
return mod; // return modulo
}
// Function to find last digit of a^b
static int LastDigit(char a[], char b[])
{
int len_a = a.length, len_b = b.length;
// if a and b both are 0
if (len_a == 1 && len_b == 1 && b[0] == '0' && a[0] == '0')
return 1;
// if exponent is 0
if (len_b == 1 && b[0] == '0')
return 1;
// if base is 0
if (len_a == 1 && a[0] == '0')
return 0;
// if exponent is divisible by 4 that means last
// digit will be pow(a, 4) % 10.
// if exponent is not divisible by 4 that means last
// digit will be pow(a, b%4) % 10
int exp = (Modulo(4, b) == 0) ? 4 : Modulo(4, b);
// Find last digit in 'a' and compute its exponent
int res = (int)(Math.pow(a[len_a - 1] - '0', exp));
// Return last digit of result
return res % 10;
}
// Driver program to run test case
public static void main(String args[]) throws IOException
{
char a[] = "117".toCharArray(), b[] = { '3' };
System.out.println(LastDigit(a, b));
}
}
// This code is contributed by Nikita Tiwari.
C#
// C# code to find last digit of a^b.
using System;
class GFG {
// Function to find b % a
static int Modulo(int a, char[] b)
{
// Initialize result
int mod = 0;
// calculating mod of b with a
// to make b like 0 <= b < a
for (int i = 0; i < b.Length; i++)
mod = (mod * 10 + b[i] - '0') % a;
// return modulo
return mod;
}
// Function to find last digit of a^b
static int LastDigit(char[] a, char[] b)
{
int len_a = a.Length, len_b = b.Length;
// if a and b both are 0
if (len_a == 1 && len_b == 1 &&
b[0] == '0' && a[0] == '0')
return 1;
// if exponent is 0
if (len_b == 1 && b[0] == '0')
return 1;
// if base is 0
if (len_a == 1 && a[0] == '0')
return 0;
// if exponent is divisible by 4
// that means last digit will be
// pow(a, 4) % 10. if exponent is
//not divisible by 4 that means last
// digit will be pow(a, b%4) % 10
int exp = (Modulo(4, b) == 0) ? 4
: Modulo(4, b);
// Find last digit in 'a' and
// compute its exponent
int res = (int)(Math.Pow(a[len_a - 1]
- '0', exp));
// Return last digit of result
return res % 10;
}
// Driver program to run test case
public static void Main()
{
char[] a = "117".ToCharArray(),
b = { '3' };
Console.Write(LastDigit(a, b));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// php code to find last digit of a^b
// Function to find b % a
function Modulo($a, $b)
{
// Initialize result
$mod = 0;
// calculating mod of b with a to make
// b like 0 <= b < a
for ($i = 0; $i < strlen($b); $i++)
$mod = ($mod * 10 + $b[$i] - '0') % $a;
return $mod; // return modulo
}
// function to find last digit of a^b
function LastDigit($a, $b)
{
$len_a = strlen($a); $len_b = strlen($b);
// if a and b both are 0
if ($len_a == 1 && $len_b == 1 &&
$b[0] == '0' && $a[0] == '0')
return 1;
// if exponent is 0
if ($len_b == 1 && $b[0] == '0')
return 1;
// if base is 0
if ($len_a == 1 && $a[0] == '0')
return 0;
// if exponent is divisible by 4 that
// means last digit will be pow(a, 4)
// % 10. if exponent is not divisible
// by 4 that means last digit will be
// pow(a, b%4) % 10
$exp = (Modulo(4, $b) == 0) ? 4 :
Modulo(4, $b);
// Find last digit in 'a' and compute
// its exponent
$res = pow($a[$len_a - 1] - '0', $exp);
// Return last digit of result
return $res % 10;
}
// Driver program to run test case
$a = "117";
$b = "3";
echo LastDigit($a, $b);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript code to find last digit of a^b
// Function to find b % a
function Modulo(a, b)
{
// Initialize result
let mod = 0;
// calculating mod of b with a to make
// b like 0 <= b < a
for (let i = 0; i < b.length; i++)
mod = (mod * 10 + b[i] - '0') % a;
return mod; // return modulo
}
// function to find last digit of a^b
function LastDigit(a, b)
{
let len_a = a.length;
let len_b = b.length;
// if a and b both are 0
if (len_a == 1 && len_b == 1 &&
b[0] == '0' && a[0] == '0')
return 1;
// if exponent is 0
if (len_b == 1 && b[0] == '0')
return 1;
// if base is 0
if (len_a == 1 && a[0] == '0')
return 0;
// if exponent is divisible by 4 that
// means last digit will be pow(a, 4)
// % 10. if exponent is not divisible
// by 4 that means last digit will be
// pow(a, b%4) % 10
exp = (Modulo(4, b) == 0) ? 4 :
Modulo(4, b);
// Find last digit in 'a' and compute
// its exponent
res = Math.pow(a[len_a - 1] - '0', exp);
// Return last digit of result
return res % 10;
}
// Driver program to run test case
let a = "117";
let b = "3";
document.write(LastDigit(a, b));
// This code is contributed by _saurabh_jaiswal
</script>
Producción :
3
Este artículo es una contribución de Shashank Mishra (Gullu) . Este artículo está revisado por el equipo geeksforgeeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA