Задача о числах Фибоначчи
Vladislav
Лимит времени 0.5 секунд
Лимит использования памяти 8 MiB
Задача можно протестировать в режиме онлайн тут.
Так как числа Фибоначчи являются довольно известной последовательностью, не имеет смысла их особое представление. Только заметит, что скорость роста n-го числа Фибоначчи можно оценить как Fn ≥ 2 ^ (n/2), при n ≥ 6. (Это факт доказывается по мат индукции).
Изучив условие, становится понятно что необходимо научиться искать последние четыре цифры N-го числа Фибоначчи, задача поиска цифрового корня является тривиальной.
Главной проблемой задачи становится ограничения на N. При таких N и ограничениях времени линейное решение является непригодным. Имеем что N ≤ 10^18, значит асимптотика O(sqrt(N)) является тоже неудовлетворительной, ибо мы получим около 10^9 действий, не считая скрытой константы, что не даст нам впихнуть это в 0.5 секунды, остается искать логарифмическое решение.
Асимптотику O(log2(N)) можно добиться благодаря одному факту.
Такую сложность можно достичь воспользовавшись одной особенностью матрицы A:
При возведение матрицы в k-ую степень, то есть имея матрицу A^k, левая верхняя ячейка будет содержать k-ое число Фибоначчи. Но умножение в лоб даст линейную сложность, естественное решение применить бинарное возведение в степень, благодаря чему получим логарифмическую сложность.
Подробно на идее бинарного возведение в степень мы не будем останавливаться, как так принцип довольно известный, и в этой задаче не играет главной роли, хотя без него решение конкретно данным способом становится невозможным.
Так как при возведение числа будут быстро переполнятся все операции будем производить по модулю 10^4, таким образом числа матрицы достаточно хранить в виде int (4 байта), и только степень матрицы типа long long (8 байт).
Теперь рассмотрим детали реализации.
Начнем с функции умножения двух матриц, которая принимает на вход две матрицы и записывает результат в первую. Обратим внимание на то что умножение не коммутативно и матрицы должны быть согласованны. Но так как конкретно в данной задаче мы работает с матрицами 2x2, согласованность предполагаем по умолчанию.
В строках 3-6 выделяется память под матрицу res, в которую запишем результат умножение matrix1 и matrix2, и позже в строках 20-24 скопируем это результат в matrix1. В строках 12-19 происходит непосредственно умножение двух матриц по модулю 10^4. В строках 25-28 освобождаем память с уже ненужной матрицы res. В итоге в matrix1 будет лежать результат умножения двух матриц.
Дальше рассмотрим функцию бинарного возведения в степень.
Функция на вход принимает два значение: матрицу и степень. Так как рекурсивная реализация бинарного возведения в степень является хвостатой рекурсией, то есть не происходит разветвления больше чем на одну ветку, есть смысл написать нерекурсивную реализацию.
В строках 2-5 выделяется память под матрицу res, в которой будет хранится результат вычисления. В строках 6-9 задаем единичную матрицу, аналог обычной единицы в поле действительных чисел. В 10 сроке имеется заголовок цикла while, который выполняется пока pow не достигнет нуля. В строках 11-15 идет непосредственно реализация бинарного возведения в степень. В строке 17 возвращается итоговый результат.
Главные функциональные участки была рассмотрены, теперь взглянем на оставшиеся функции.
Функция last_four_digit используют для вызова бинарного возведения в степень для нашей матрицы и возвращает результат левой верхней ячейка (a[0][0]).
Функция digital_sqrt напрямую реализует вычисление цифрового корня.
Остается небольшой кусок кода который отвечает за считывание с клавиатуры и вывод результата.
Ниже привожу полный код решение задачи на С++:
#include <cassert>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const long long MOD = 10000, nsize = 2;
void mul_matrix(int ** matrix1, int ** matrix2) {
//res -> matrix1
int ** res = new int *[nsize];
for (int i = 0; i < nsize; i++) {
res[i] = new int[nsize];
}
for (int i = 0; i < nsize; i++) {
for (int j = 0; j < nsize; j++) {
res[i][j] = 0;
}
}
for (int i = 0; i < nsize; i++) {
for (int j = 0; j < nsize; j++) {
for (int k = 0; k < nsize; k++) {
res[i][j] += matrix1[i][k] * matrix2[k][j];
}
res[i][j] %= MOD;
}
}
for (int i = 0; i < nsize; i++) {
for (int j = 0; j < nsize; j++) {
matrix1[i][j] = res[i][j];
}
}
for (int i = 0; i < nsize; i++) {
delete[] res[i];
}
delete res;
return;
}
int ** bpow(int ** matrix, long long pow) {
int ** res = new int *[nsize];
for (int i = 0; i < nsize; i++) {
res[i] = new int[nsize];
}
res[0][0] = 1;
res[0][1] = 0;
res[1][0] = 0;
res[1][1] = 1;
while (pow) {
if (pow & 1) {
mul_matrix(res, matrix);
}
mul_matrix(matrix, matrix);
pow /= 2;
}
return res;
}
int last_four_digit(long long f_n) {
if (f_n == 0) {
return 1;
}
int ** p = new int *[nsize];
for (int i = 0; i < nsize; i++) {
p[i] = new int[nsize];
}
p[0][0] = 1;
p[0][1] = 1;
p[1][0] = 1;
p[1][1] = 0;
int ** r = bpow(p, f_n);
return r[0][0];
}
int digital_sqrt(int n) {
int sum = 0;
while (n >= 10) {
sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
n = sum;
}
return n;
}
int main() {
long long n;
while (cin >> n) {
cout << digital_sqrt(last_four_digit(n)) << "\n";
}
return 0;
}
Освоим навык решения такой задачи, мы кроем довольно широкий спектр задач, где ограничение на N доходит до 10^18 и просят производить действия с последними числами числа.
Довольно тесная задача, но решаемая кардинально другим способом, где требуется действия с первыми k цифрами n-го числа Фибоначчи, решение подобных задач будет рассмотрено в следующей статье.
Спасибо за внимание.