primeros y últimos k dígitos del número n^n

Question

he escrito un código C++ para generar los primeros y últimos dígitos k de un número tan grande como 10^9. (k < = 9).

cin>>n>>k; 
    cout << (unsigned long)floor(pow(10.0, modf(n*log10((double)n), &dummy) + k - 1)) << " "; // code that prints the first k digits 
    long long int ans = foo(n,k); // function that prints the last k digits 
    if(ans==0) 
    { 
    for(int i=0;i<k;i++) cout << "0"; 
    } 
    else{ 
      stringstream ss; 
      string s; 
      ss<<ans; 
      ss>>s; 
      if(s.size()!=k) 
      { 
       for(int i=0;i<(k-s.size());i++) 
      s="0"+s; 
      } 
      cout<<s; 
    } 

donde la función foo() es:

long long int foo(int n, int k) // code of the function 
{ 
    long long int m=1; 
    for(; k > 0; k--) m*=10; 

    long long int r=1, t=n % m; 
    while(n) 
    { 
    if (n % 2) 
     r = r * t % m; 
    t = t * t % m; 
    n >>= 1; 
    } 

    return r; 
} 

esto me da salida como: si se les da 9 y 3 como entradas, que da primero y 3 últimos dígitos del 9 al poder 9 (9^9) es decir, 387 y 489. Pero aún me faltan algunos casos de prueba. ¿Alguien puede ayudarme a encontrar el caso de prueba para el cual mi código no funcionaría?

1 ≤ n ≤ 109, 1 ≤ k ≤ 9 el enunciado del problema: http://www.codechef.com/problems/MARCHA4/

Answer 1

Si n^n <= 10^9, en cuyo caso el código parece funcionar bien. Sin embargo, si permite mayores n, digamos 11^11, y solicite los últimos 4 dígitos de eso, que son 0611, su código solo imprimirá 611. Básicamente, no imprime ceros a la izquierda cuando debería.

Answer 2

Supongamos que k = 9. Ahora, m = 1e9 y t <= 1e9 - 1. t * t puede ser tan alto como 1e18 - 2e9 + 1, que necesita ... 59.8 bits.

Ok, no es un problema con un long long int de 64 bits, que tiene 63 bits de magnitud (y 1 de signo), pero lo dejaré aquí para que otros no repitan el mismo análisis.

Answer 3

Esto realmente no responde la pregunta, y es casi trivialmente fácil, pero creo que valdría la pena compartirlo. Si hubiera una función de "comentario largo", la estaría usando.

EDIT: acabo de notar usando str en lugar de repr eliminará la L en su propia

def firstAndLastDig(k, num): 
    s = str(num) 
    return (s[:k], s[-k:]) 

def firstAndLastDigSelfExp(k,n): 
    return firstAndLastDig(k,n**n) 

desbordamiento no es un problema (lo único que se ocupa de la L si se utiliza repr en lugar de str),

firstAndLastDigSelfExp(6,12) 
('891610', '448256') 

firstAndLastDigSelfExp(42,491) 
('209417336844579728122309696211520194012462', '160453713040914743773217804810667483135091') 

y tampoco lo son los ceros iniciales

>>> firstAndLastDigSelfExp(4,9) 
('3874', '0489') 

Esto no se lo digas la l modular y las cosas no son geniales, al contrario, me gustó mucho leer sobre cómo lo hizo sin generar el número completo. No sabía nada sobre modf hasta que leí la pregunta de OP y el cuerpo de foo es muy interesante.

Answer 4

¿Le dijeron que n es un número entero positivo? Por ejemplo, (-8)^(-8) es perfectamente expresable en decimales pero su programa no puede manejarlo.

Answer 5

Creo que el problema es utilizar punto flotante. Encontrar el primer dígito de un número en realidad requiere una precisión perfecta.

Desafortunadamente, el juez del concurso evidentemente no comprende ese "número de dígitos significativos"! = "Número de dígitos correctos".

Tal vez hay algo de forma inteligente para calcular exactamente (n * n, n = 10 * 9) sin agotar la memoria, pero encontrar los primeros dígitos de una muy buena estimación no es simplemente lo mismo que encontrar los primeros dígitos de la respuesta.