큰 숫자에 대한 A^B의 마지막 자릿수 찾기

GfG Practice에서 사용해 보세요. ' title=

밑수 a(1이 되는 자릿수 d) 두 개의 정수가 주어집니다.<= d <= 1000) and the index b (0 <= b <= 922*10^15). You have to find the last digit of a^b.
예:

Input : 3 10  
Output : 9  
  
Input : 6 2  
Output : 6  
  
Input : 150 53  
Output : 0

몇 가지 예를 살펴보면 아래 패턴을 확인할 수 있습니다.

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

주어진 표에서 우리는 사이클 반복의 최대 길이가 4임을 알 수 있습니다.
예: 2*2 = 4*2 = 8*2 = 16*2 = 32 32의 마지막 숫자는 2입니다. 이는 4를 곱한 후 숫자가 반복된다는 의미입니다. 따라서 알고리즘은 매우 간단합니다.
원천 : Brilliants.org
알고리즘 :

부터 숫자 매우 크므로 문자열로 저장합니다.
기본 a의 마지막 숫자를 가져옵니다.
이제 b%4를 계산해 보세요. 여기서 b는 매우 크다.
- b%4==0이면 b가 4로 완전히 나누어진다는 의미이므로 이제 지수는 exp = 4가 됩니다. 왜냐하면 숫자에 4를 곱하면 위 다이어그램의 주기 표에 따라 마지막 숫자를 얻게 되기 때문입니다.
- b%4!=0이면 b가 4로 완전히 나누어지지 않음을 의미하므로 이제 지수는 exp=b%4가 됩니다. 왜냐하면 숫자 지수를 곱하면 위 다이어그램의 주기 표에 따라 마지막 숫자를 얻게 되기 때문입니다.
- 이제 ldigit = pow( last_digit_in_base exp )를 계산해 보세요.
- a^b의 마지막 숫자는 ldigit%10입니다.

아래는 위의 알고리즘을 구현한 것입니다.

C++

// C++ code to find last digit of a^b #include    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.

Python

def last_digit(a b): a = int(a) b = int(b) # if a and b both are 0 if a == 0 and b == 0: return 1 # if exponent is 0 if b == 0: return 1 # if base is 0 if a == 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 if b % 4 == 0: res = 4 else: res = b % 4 # Find last digit in 'a' and compute its exponent num = pow(a res) # Return last digit of num return num % 10 a = '117' b = '3' print(last_digit(ab)) # This code is contributed by Naimish14.

// 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.

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>

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. ?>

출력 :

이 기사는 geeksforgeeks 팀이 검토했습니다.

TechCodeview

큰 숫자에 대한 a^b의 마지막 자릿수 찾기