Tous les défis
Facile 0 résolus 0 % de réussite

Derniers chiffres de la somme des n^n

Trouver les k derniers chiffres de 1^1 + 2^2 + ... + n^n.

Ce que vous allez apprendre

  • Réduire sommes et produits modulo 10^k
  • Calculer des puissances par exponentiation rapide
  • Formater un nombre avec des zéros en tête

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

Exemple 1
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".

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.