Problema
A soma 1^1 + 2^2 + 3^3 + ... + n^n tem milhares de dígitos mesmo para n moderado, mas só o final dela interessa. Encontre os seus últimos k dígitos. Trabalhe módulo 10^k desde o início: reduza depois de cada multiplicação e de cada soma, e os números continuam pequenos.
Implemente self_powers_tail(n, k).
Entrada
n: o último termo da soma.
k: quantos dígitos finais retornar.
Saída
Retorne os últimos k dígitos como uma string de exatamente k caracteres, completada com zeros à esquerda se necessário.
Restrições
1 ≤ n ≤ 5000; 1 ≤ k ≤ 9
Exemplos
Entrada:
n = 4
k = 3
Saída esperada:
expected = "288"
Entrada:
long long n = 4;
long long k = 3;
Saída esperada:
std::string expected = "288";
Entrada:
long n = 4;
long k = 3;
Saída esperada:
string expected = "288";
Explicação
1 + 4 + 27 + 256 = 288, então os três últimos dígitos são "288".
Entrada:
n = 3
k = 4
Saída esperada:
expected = "0032"
Entrada:
long long n = 3;
long long k = 4;
Saída esperada:
std::string expected = "0032";
Entrada:
long n = 3;
long k = 4;
Saída esperada:
string expected = "0032";
Explicação
1 + 4 + 27 = 32, completado para quatro dígitos: "0032".
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Só os últimos k dígitos importam, então reduza módulo 10^k depois de cada passo.
Dica 2
i^i pode ser calculado por quadrados sucessivos ou multiplicando i vezes com redução.
Dica 3
Complete o valor final com zeros à esquerda para obter exatamente k caracteres.
Complexidade esperada
tempo O(n log n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.