Problème
La somme 1^1 + 2^2 + 3^3 + ... + n^n compte des milliers de chiffres même pour un n modeste, mais seule sa fin nous intéresse. Trouvez ses k derniers chiffres. Travaillez modulo 10^k dès le départ : réduisez après chaque multiplication et chaque addition, et les nombres restent petits.
Implémentez self_powers_tail(n, k).
Entrée
n : le dernier terme de la somme.
k : le nombre de chiffres de fin à renvoyer.
Sortie
Renvoyez les k derniers chiffres sous forme d'une chaîne d'exactement k caractères, complétée par des zéros à gauche si nécessaire.
Contraintes
1 ≤ n ≤ 5000 ; 1 ≤ k ≤ 9
Exemples
Entrée :
n = 4
k = 3
Sortie attendue :
expected = "288"
Entrée :
long long n = 4;
long long k = 3;
Sortie attendue :
std::string expected = "288";
Entrée :
long n = 4;
long k = 3;
Sortie attendue :
string expected = "288";
Explication
1 + 4 + 27 + 256 = 288, donc les trois derniers chiffres sont "288".
Entrée :
n = 3
k = 4
Sortie attendue :
expected = "0032"
Entrée :
long long n = 3;
long long k = 4;
Sortie attendue :
std::string expected = "0032";
Entrée :
long n = 3;
long k = 4;
Sortie attendue :
string expected = "0032";
Explication
1 + 4 + 27 = 32, complété sur quatre chiffres : "0032".
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Seuls les k derniers chiffres comptent, donc réduisez modulo 10^k après chaque étape.
Indice 2
i^i se calcule par exponentiation rapide, ou en multipliant i fois avec réduction.
Indice 3
Complétez la valeur finale par des zéros à gauche pour obtenir exactement k caractères.
Complexité attendue
temps O(n log n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.