Сумма 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
Примеры
Ввод:
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".
Ввод:
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. Следуйте условию и ограничениям выше.