Calculando el último dígito de A ^ B donde A y B son números muy grandes -- ++ camp codereview Relacionados El problema

Calculating the last digit of a^b where a and b are very large numbers


3
vote

problema

Español

Tengo que hacer código que calcula el último dígito de $ A ^ B $. Aquí, $ A $ puede tener hasta 1000 dígitos, mientras que $ B $ puede ser de 0 a 915 * 10 15 . Ahora calculé el último dígito de pop1 y recaudó que el número de un solo dígito a la potencia pop2 y el último dígito del número serán la respuesta.

  pop3  

Sin embargo, no sé por qué esto muestra WA al enviarlo? ¿Algún casos de esquina que me podría perder?

Original en ingles

I have to make code that calculates the last digit of \$a^b\$. Here, \$a\$ can have up to 1000 digits whereas \$b\$ can be from 0 to 915*1015. Now I calculated the last digit of a and raised that single digit number to the power b and that number's last digit will be the answer.

#include <iostream> #include <math.h> #include <string> using namespace std; unsigned long long int foo (unsigned long long int a,unsigned long long int b ); int main (void) {     int test;     cin>>test;     while ( test != 0 )     {         string a;         cin>>a;         unsigned long long int b;         cin>>b;         char c;         int e;         string::iterator it = a.end()-1;         c = *it;         e = c -48;         if ( e == 0 && b == 0 )             cout<<"0"<<"\n";         else         {             unsigned long long modu  = foo(e,b);             cout<<modu<<"\n";             test--;         }     }     return 0; }    unsigned long long int foo (unsigned long long int a,unsigned long long int b ) {     unsigned long long int ret;     if ( b == 0 )         return 1;     if ( b % 2 == 0 )     {         ret = foo(a,b/2);         ret = ret*ret;     }     else if ( b % 2 != 0 )     {         ret = foo(a,b/2);         ret = ret*ret;         ret = ret*a;     }     return ret%10; } 

However, I don't know why this shows WA on submitting it? Any corner cases that I might be missing?

  

Lista de respuestas

5
 
vote
vote
La mejor respuesta
 

Respuesta incorrecta

$$ todo ^ 0 = 1 = & gt; 0 ^ 0 = 1 $$

  T top() const4  

SOLUCIÓN

Relé del último dígito solo en el último dígito y no puede ver los dígitos que la anterior. Como su poder está a la altura de $ 10 ^ {18} $, debe usar la función de alimentación binaria modular.

Aquí está mi solución:

  T top() const5  

c ++ 11 std :: cadena

Dado que C ++ 11 T top() const6 tenía un método < Código> T top() const7 que devuelve el último char en la cadena.

Para hacer esto con C ++ 98 puede usar T top() const8 < / Código> iterator.

Solución con complejidad $ O (1) $

El código anterior puede ser una solución aceptable, pero si aún no será suficiente, intente establecer una matriz predefinida para la longitud del círculo cuando

$$ A ^ {longitud} mod (10) = a | a = [0 ldots 9] $$

Escribiría un poco de script de Python, echemos un vistazo a los resultados:

  T top() const9  

¿Qué significa? El primer número es el dígito que se procesó. La matriz es la matriz de dígitos más bajos de la ecuación anterior. Como puede ver, no hay demasiados círculos de repeticiones.

Veamos el Dígito 2:

  • con poder de 1 tenemos $ 2 ^ 1 mod (10) = 2 $
  • con poder de 2 tenemos $ 2 ^ 2 mod (10) = 4 $
  • con poder de 3 tenemos $ 2 ^ 3 mod (10) = 8 $
  • con poder de 4 tenemos $ 2 ^ 4 mod (10) = 6 $
  • con poder de 5 tenemos $ 2 ^ 5 mod (10) = 2 $

Eso es todo, tenemos el círculo para Dígito 2.

También se pueden agrupar los dígitos por número de poderes antes de repetirse el dígito inferior.

  • 2, 3, 7, 8 repetidos después de 4 operaciones de energía
  • 1, 5, 6 repetido después de cada opeta de alimentación
  • 4, 9 repitió cada segunda operación de alimentación
  void pop()0  
 

Wrong answer

$$ everything^0 = 1 => 0^0 = 1$$

    if ( e == 0 && b == 0 )         cout<<"0"<<"\n"; 

Solution

Last digit relay only on last digit and you can not look at digits than goes before last one. As your power is up to \$10^{18}\$ you have to use modular binary power function.

Here is my solution:

#include <iostream> #include <string>  typedef unsigned long long int ULLI; typedef unsigned int UI;  UI bin_pow(UI a, ULLI n) {     UI result = 1;     while (n) {         if (n & 1) {             result = (result * a) % 10;             n -= 1;         } else {             a = (a * a) % 10;             n >>= 1;         }     }     return result; }  int main(int argc, char *argv[]) {     int n;     std::cin >> n;     while (n--) {         std::string a;         ULLI b;         std::cin >> a >> b;         std::cout << bin_pow(a.back() - '0', b) << std::endl;     } } 

C++11 std::string

Since C++11 std::basic_string had method .back() that returns last char in the string.

To do this with C++98 you can use .rbegin() iterator.

Solution with complexity \$O(1)\$

Previous code can be acceptable solution, but if it will still not be enough, try to set predefined array for length of circle when

$$ a^{length} mod(10) = a | a = [0 \ldots 9]$$

I'd write some Python script, lets take a look at the results:

(2, [2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8]) (3, [3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7]) (4, [4, 6, 4, 6, 4, 6, 4, 6, 4, 6, 4]) (5, [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]) (6, [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]) (7, [7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3]) (8, [8, 4, 2, 6, 8, 4, 2, 6, 8, 4, 2]) (9, [9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9]) 

What does it means? First number is the digit which was processed. Array is array of lower digits from previous equation. As you can see, there are not too many circles of repetitions.

Lets take a look at digit 2:

  • with power of 1 we have \$2^1 mod(10)=2\$
  • with power of 2 we have \$2^2 mod(10)=4\$
  • with power of 3 we have \$2^3 mod(10)=8\$
  • with power of 4 we have \$2^4 mod(10)=6\$
  • with power of 5 we have \$2^5 mod(10)=2\$

that's it, we've got the circle for digit 2.

Also digits may be grouped by number of powers before lower digit will be repeated.

  • 2, 3, 7, 8 repeated after 4 power operations
  • 1, 5, 6 repeated after each power opetation
  • 4, 9 repeated each 2nd power operation
const unsigned int predefined[10][4] = {     {0},     {1},     {2,4,8,6},     {3,9,7,1},     {4,6},     {5},     {6,4},     {7,9,3,1},     {8,4,2,6},     {9,1} };  unsigned int bin_pow(const unsigned int& a, unsigned long long int n) {     if (!n) return 1;      switch(a) {         case 0:         case 1:         case 5:             return a;         case 2:         case 4:         case 7:         case 8:             return predefined[a][n & 3];         default:             return predefined[a][n & 1];     } } 
 
 
         
         

Relacionados problema

1  Piedra Papel tijeras  ( Rock paper scissors ) 
Gracias por su tiempo, soy nuevo en la programación y pasé algunos días haciendo este rock, papel y amp; Juego de tijera. ¿Qué otras mejoras posibles podrían ...

10  Quicksort  ( Templated quicksort ) 
original quicksort.h #include <algorithm> namespace quicksort { template <typename iterator, typename value_type> struct traits { static iterato...

2  Simplifique el código de verificación de banderas de bits  ( Simplify bit flags checking code ) 
Por favor, ayuda a hacer que este código sea más limpio. Es parte del procedimiento de la ventana que notifica a mi renderizado antes de Área de cliente de ...

3  Implementación más portátil de Tolower ()  ( More portable tolower implementation ) 
Me estoy desafiando a intentar intentar escribir una función que sea tan eficiente, portátil y a prueba de fallas posible. La función es muy simple y solo con...

14  Implementando una lista relacionada adecuada para un entorno profesional  ( Implementing a proper linked list for a professional environment ) 
Tengo algunas preocupaciones: ¿Es normal que la clase tenga al menos un nodo? En otras palabras, esta implementación no puede tener una lista vinculada va...

4  Simulación simple de red neural en C ++ (Ronda 2)  ( Simple neural network simulation in c round 2 ) 
Intro Ayer He publicado esta pregunta . Desde entonces, he actualizado mi código para incorporar estas sugerencias . También he eliminado la dependencia d...

1  Integración de oscilador de fase perturbada  ( Perturbed phase oscillator integration ) 
Estoy integrando un sistema de osciladores de fase perturbados. Defino el sistema de ecuación y también la matriz jacobiana. Tengo que remodelar el vector dim...

21  Algoritmo de suma de comprobación personalizada  ( Custom checksum algorithm ) 
A MIENTROS RUENTANDO, INVERSO: diseñé un algoritmo de suma de comprobación de una MMO que se usa para comprobar el Validez de un artículo que está vinculado...

9  Entrada de usuario y lectura de contenidos de archivo  ( User input and reading contents of file ) 
Para la divulgación completa: esta es una tarea para mi clase de programación y solo quiero consejos o consejos sobre algunos del código. Detalles de asigna...

0  Sistema de gestión de la biblioteca en C ++  ( Library management system in c ) 
Estoy haciendo un proyecto de principiante C ++ y es simplemente un sistema de administración de la biblioteca donde contratará un estudiante, devolver un lib...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos