Последовательность чисел

243
23 марта 2018, 12:57

Есть задача, ее я решил и пока программа работает с маленькими числами ответы выводит правильно. Но когда мы берем более большие числа ответы перестает считать.

Я использовал переменные типа unsigned __int64. И все равно большие последовательности считает неправильно. В чем может быть проблема?

Задача: Последовательность чисел, определена формулой:

F (0) = a
F (1) = b
F (N) = F (N-1) + F (N-2)

В каждой строке нам даны a, b, N и M.

Надо вывести остаток от N-нного члена последовательности деленного на 10M.

Примеры Ввода/Вывода:

код:

#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
    unsigned __int64 a,b,n,m,sum,po;
    cin>>a>>b>>n>>m;
    sum=a+b;
    po=pow(10,m);
    if(n==0){cout<<a<<endl;}
    else if(n==1){cout<<b%po<<endl;}
    else if(n==2){cout<<sum%po<<endl;}
    else if(n>=3){
        for(unsigned __int64 i=2;i<n;i++)
        {
        sum+=b;
        b=sum-b;
        }
        cout<<sum%po<<endl;
    }
return 0;
}
Answer 1

Вам нужно считать не сами значения чисел Фибоначчи, а их остатки - вычисляя их сразу же по ходу дела. Грубо говоря, остаток от деления некоторого числа Фибоначчи равен сумме остатков двух предыдущих чисел.

Не уверен, что будет корректно приводить решение олимпиадной задачи, но, думаю, этого намека должно вполне хватить.

Это решение "в лоб"; имеет смысл отслеживать периодичность появления остатков - а они обязательно будут при N большем 102M+1 - это может существенно ускорить работу при больших N. Я не знаю, какие ограничения по времени - но считать миллиардное число Фибоначчи (в смысле, остаток) - времени может и не хватить. Посмотрите здесь материал об остатках.

READ ALSO
Как сделать тоже самое с помощью адресации?

Как сделать тоже самое с помощью адресации?

Задан массив char str[stolb][dlina]; а также:

279
Console Diary - дневник в консоли

Console Diary - дневник в консоли

Сделал свой второй небольшой, но интересный проект, дневник в консолиВсе записи сохраняются в файлах с именами по дате создания

213
Метод сортировки &ldquo;Шейкерный&rdquo; (C++)

Метод сортировки “Шейкерный” (C++)

Доброго времени сутокЕсть такая задача:

265
Заполнение области сферами

Заполнение области сферами

Существуют ли готовые алгоритмы по заполнению области сферами различных радиусов?

197