Вывод номера первого числа Фибоначчи, кратного N
Задача состоит в выводе номера первого числа Фибоначчи, кратного N. Проблема в том, что для некоторых N искомое число Фиббоначи слишком большое, и не укладывается в стандартные типы данных C++(long long). Есть ли способ каким-либо образом оптимизировать работу алгоритма? Входное N не должно быть больше 1000.
Ответы (1 шт):
Автор решения: Harry
→ Ссылка
А зачем вы пытаетесь вычислить сами числа Фибоначчи? Вам достаточно вычислять остатки от деления на это число N.
int fibmod(int N)
{
int no = 1;
for(int a = 0, b = 1; b; ++no)
{
int c = (a+b)%N;
a = b; b = c;
}
return no;
}
Ну, т.е. вычисляем числа по модулю и фиксируем номер числа, пока очередное число не окажется равным нулю - тогда возвращаем этот номер.
Так что метку большие-числа я с вопроса сниму - нет тут таких...