Einfach 0 gelöst 0% Erfolgsquote

Self Powers Tail

Find the last k digits of 1^1 + 2^2 + ... + n^n.

Das lernst du

  • Reduce sums and products modulo 10^k
  • Compute powers with repeated squaring
  • Format a number with leading zeros

Problem

Übersetzung anzeigen

The sum 1^1 + 2^2 + 3^3 + ... + n^n has thousands of digits even for modest n, but only its tail is needed. Find its last k digits. Work modulo 10^k from the start: reduce after every multiplication and every addition, and the numbers stay small.

Implement self_powers_tail(n, k).

Input

n: The last term of the sum.

k: How many trailing digits to return.

Output

Return the last k digits as a string of exactly k characters, padded with leading zeros if needed.

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, so the last three digits are "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, padded to four digits: "0032".

So gehst du vor

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

Hinweis 1

Only the last k digits matter, so reduce modulo 10^k after every step.

Hinweis 2

i^i can be found by repeated squaring, or by multiplying i times with reduction.

Hinweis 3

Pad the final value on the left with zeros to get exactly k characters.

Erwartete Komplexität

O(n log n) time, O(1) extra space

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.