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

GfG Practice에서 사용해 보세요.
밑수 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  (  a    b  ))   # This code is contributed by Naimish14.   
  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.   
  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.   ?>   
       출력 :     
  3    
 이 기사는 geeksforgeeks 팀이 검토했습니다.