Есть задача, ее я решил и пока программа работает с маленькими числами ответы выводит правильно. Но когда мы берем более большие числа ответы перестает считать.
Я использовал переменные типа 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;
}
Вам нужно считать не сами значения чисел Фибоначчи, а их остатки - вычисляя их сразу же по ходу дела. Грубо говоря, остаток от деления некоторого числа Фибоначчи равен сумме остатков двух предыдущих чисел.
Не уверен, что будет корректно приводить решение олимпиадной задачи, но, думаю, этого намека должно вполне хватить.
Это решение "в лоб"; имеет смысл отслеживать периодичность появления остатков - а они обязательно будут при N большем 102M+1 - это может существенно ускорить работу при больших N. Я не знаю, какие ограничения по времени - но считать миллиардное число Фибоначчи (в смысле, остаток) - времени может и не хватить. Посмотрите здесь материал об остатках.
Сборка персонального компьютера от Artline: умный выбор для современных пользователей