Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Endziffern der Selbstpotenzen

Finde die letzten k Ziffern von 1^1 + 2^2 + ... + n^n.

Das lernst du

  • Summen und Produkte modulo 10^k reduzieren
  • Potenzen durch wiederholtes Quadrieren berechnen
  • Eine Zahl mit führenden Nullen formatieren

Problem

Die Summe 1^1 + 2^2 + 3^3 + ... + n^n hat schon für mäßig große n Tausende Stellen, gebraucht werden aber nur die letzten. Finde ihre letzten k Ziffern. Rechne von Anfang an modulo 10^k: Wenn du nach jeder Multiplikation und jeder Addition reduzierst, bleiben die Zahlen klein.

Implementiere self_powers_tail(n, k).

Eingabe

n: Das letzte Glied der Summe.

k: Wie viele Endziffern zurückgegeben werden.

Ausgabe

Gib die letzten k Ziffern als String mit genau k Zeichen zurück, bei Bedarf vorne mit Nullen aufgefüllt.

Einschränkungen

1 ≤ n ≤ 5000; 1 ≤ k ≤ 9

Beispiele

Beispiel 1
Eingabe:
n = 4
k = 3

Erwartete Ausgabe:
expected = "288"
Eingabe:
long long n = 4;
long long k = 3;

Erwartete Ausgabe:
std::string expected = "288";
Eingabe:
long n = 4;
long k = 3;

Erwartete Ausgabe:
string expected = "288";

Erläuterung

1 + 4 + 27 + 256 = 288, die letzten drei Ziffern sind also "288".

Beispiel 2
Eingabe:
n = 3
k = 4

Erwartete Ausgabe:
expected = "0032"
Eingabe:
long long n = 3;
long long k = 4;

Erwartete Ausgabe:
std::string expected = "0032";
Eingabe:
long n = 3;
long k = 4;

Erwartete Ausgabe:
string expected = "0032";

Erläuterung

1 + 4 + 27 = 32, auf vier Stellen aufgefüllt: "0032".

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Nur die letzten k Ziffern zählen, reduziere also nach jedem Schritt modulo 10^k.

Hinweis 2

i^i bekommst du durch wiederholtes Quadrieren oder indem du i-mal multiplizierst und jedes Mal reduzierst.

Hinweis 3

Fülle den Endwert links mit Nullen auf, bis er genau k Zeichen hat.

Erwartete Komplexität

Zeit O(n log n), zusätzlicher Speicher O(1)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.