Etsi suurille numeroille a^b:n viimeinen numero
Kokeile GfG Practicessa 
Sinulle annetaan kaksi kokonaislukua, joiden kanta on a (numeroiden d määrä siten, että 1 <= d <= 1000) and the index b (0 <= b <= 922*10^15). You have to find the last digit of a^b.
Esimerkkejä:
Input : 3 10
Output : 9
Input : 6 2
Output : 6
Input : 150 53
Output : 0
Muutaman esimerkin ottamisen jälkeen voimme huomata alla olevan kaavan.
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
Annetusta taulukosta näemme, että syklin toiston enimmäispituus on 4.
Esimerkki: 2*2 = 4*2 = 8*2 = 16*2 = 32:n viimeinen numero on 2, mikä tarkoittaa, että 4-kertaisen numeron kertomisen jälkeen luku toistaa itsensä. Joten algoritmi on hyvin yksinkertainen.
Lähde: Brilliants.org
Algoritmi:
- Koska määrä ovat erittäin suuria, säilytämme ne merkkijonona.
- Ota kantaluvun a viimeinen numero.
- Laske nyt b%4. Tässä b on erittäin suuri.
- Jos b%4==0, se tarkoittaa, että b on täysin jaollinen 4:llä, joten eksponenttimme on nyt exp = 4, koska kertomalla luku 4 kertaa saamme viimeisen luvun yllä olevan kaavion syklitaulukon mukaisesti.
- Jos b%4!=0, se tarkoittaa, että b ei ole täysin jaollinen 4:llä, joten eksponenttimme on nyt exp=b%4, koska kertomalla lukujen eksponentti kertaa saadaan viimeinen numero yllä olevan kaavion syklitaulukon mukaisesti.
- Laske nyt ldigit = pow(viimeinen_numero_peruslauseessa).
- Kohteen a^b viimeinen numero on ldigit%10.
C++
Alla on yllä olevan algoritmin toteutus.
Java// C++ code to find last digit of a^b #includeusing 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 ; } Python// 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#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 ( a b )) # This code is contributed by Naimish14.JavaScript// 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< 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>Lähtö:
3
Tämän artikkelin ovat arvioineet tiimin geeksforgeeks.
