Dostanete dvě celá čísla se základem a (počet číslic d takový, že 1<= d <= 1000) and the index b (0 <= b <= 922*10^15). You have to find the last digit of a^b.
Příklady:
Input : 3 10
Output : 9
Input : 6 2
Output : 6
Input : 150 53
Output : 0
Po několika příkladech si můžeme všimnout níže uvedeného vzoru.
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
V uvedené tabulce vidíme, že maximální délka pro opakování cyklu je 4.
Příklad: 2*2 = 4*2 = 8*2 = 16*2 = 32 poslední číslice v 32 je 2, což znamená, že po vynásobení 4 krát se číslice opakují. Algoritmus je tedy velmi jednoduchý.
zdroj: Brilliants.org
Algoritmus:
- Od číslo jsou velmi velké, ukládáme je jako řetězec.
- Vezměte poslední číslici v základu a.
- Nyní vypočítejte b%4. Zde b je velmi velké.
- Pokud b%4==0 znamená to, že b je zcela dělitelné 4, takže náš exponent nyní bude exp = 4, protože vynásobením čísla 4 krát dostaneme poslední číslici podle tabulky cyklu ve výše uvedeném diagramu.
- Pokud b%4!=0, znamená to, že b není zcela dělitelné 4, takže náš exponent nyní bude exp=b%4, protože vynásobením exponentu čísla krát dostaneme poslední číslici podle tabulky cyklu ve výše uvedeném diagramu.
- Nyní vypočítejte ldigit = pow( last_digit_in_base exp ).
- Poslední číslice a^b bude ldigit%10.
Níže je implementace výše uvedeného algoritmu.
C++
// C++ code to find last digit of a^b #include
// 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.
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.
<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 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. ?> výstup:
3
Tento článek je recenzován týmem geeksforgeeks.