Все задачи
Легко Решено: 0 Процент решений: 0%

Последние цифры суммы самостепеней

Найдите последние k цифр числа 1^1 + 2^2 + ... + n^n.

Чему вы научитесь

  • Брать суммы и произведения по модулю 10^k
  • Вычислять степени многократным возведением в квадрат
  • Дополнять число ведущими нулями

Условие

Сумма 1^1 + 2^2 + 3^3 + ... + n^n даже при небольших n содержит тысячи цифр, но нам нужен только её конец. Найдите её последние k цифр. С самого начала работайте по модулю 10^k: берите остаток после каждого умножения и каждого сложения, и числа останутся маленькими.

Реализуйте self_powers_tail(n, k).

Входные данные

n: последний член суммы.

k: сколько последних цифр нужно вернуть.

Выходные данные

Верните последние k цифр в виде строки ровно из k символов, при необходимости дополненной ведущими нулями.

Ограничения

1 ≤ n ≤ 5000; 1 ≤ k ≤ 9

Примеры

Пример 1
Ввод:
n = 4
k = 3

Ожидаемый вывод:
expected = "288"
Ввод:
long long n = 4;
long long k = 3;

Ожидаемый вывод:
std::string expected = "288";
Ввод:
long n = 4;
long k = 3;

Ожидаемый вывод:
string expected = "288";

Пояснение

1 + 4 + 27 + 256 = 288, поэтому последние три цифры - "288".

Пример 2
Ввод:
n = 3
k = 4

Ожидаемый вывод:
expected = "0032"
Ввод:
long long n = 3;
long long k = 4;

Ожидаемый вывод:
std::string expected = "0032";
Ввод:
long n = 3;
long k = 4;

Ожидаемый вывод:
string expected = "0032";

Пояснение

1 + 4 + 27 = 32, дополняем нулями до четырёх цифр: "0032".

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Важны только последние k цифр, поэтому после каждого шага берите остаток по модулю 10^k.

Подсказка 2

i^i можно найти многократным возведением в квадрат или умножив i раз с взятием остатка.

Подсказка 3

Дополните итоговое значение нулями слева, чтобы получилось ровно k символов.

Ожидаемая сложность

время O(n log n), доп. память O(1)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.