Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.61
Lord_Voodoo
Супер-модератор
8580 / 2180 / 61
Регистрация: 07.03.2007
Сообщений: 10,864
Завершенные тесты: 1
#1

Остаток деления от числа фибоначчи - C++

11.10.2008, 11:56. Просмотров 2193. Ответов 0
Метки нет (Все метки)

подскажите, как максимально минимизировать такой алгоритм:
Код
#include <iostream>
using namespace std;
const int N = 2;
void mult(long long a[N][N], long long b[N][N], long long res[N][N], long long d){
  long long c[N][N] = {0, 0, 0, 0};
  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++){
      c[i][j] = 0;
      for(int k = 0; k < N; k++)
        c[i][j] = (c[i][j] + (a[i][k] % d)*(b[k][j] % d)) % d;
      c[i][j] = c[i][j] % d;
    }
  memmove(res, c, 4 * sizeof(long long));
}
int main()
{
    long long mp[N][N] = {0, 1, 1, 1};
    long long mr[N][N] = {1, 0, 0, 1};
    long long n, d;
    cin>>n>>d;
    if(n <= 2){
      cout<<1 % d;
      return 0;
    }
    while(n > 0){
      if((n & 1) == 0){
        mult(mp, mp, mp, d);
        n >>= 1;
      }
      n--;
      mult(mr, mp, mr, d);
    }
    cout<<mr[0][1]<<endl;
 return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2008, 11:56     Остаток деления от числа фибоначчи
Посмотрите здесь:
C++ Вывести остаток от деления НОД чисел F(i) и F(j) на 10^9. (F - Число Фибоначчи)
Очень большие числа: узнать, есть ли остаток от деления одного числа на другое C++
Остаток от деления целого числа C++
C++ Напишите программа, которая вводит два целых числа и выводит на экран остаток от деления первого числа на втор
Остаток от деления, числа в виде массивов C++
C++ Как получить остаток от деления целго числа?
C++ даны целые числа A, B и C. Выведите остаток от деления AB (A в степени B) на C
Найти остаток от деления одного целого числа на другое C++
Вывести остаток от деления натурального числа на пять прописью C++
C++ Даны натуральные числа a1,a2,.,an . Указать те из них, у которых остаток от деления на M равен L (0< L< M
C++ C++ даны целые числа а1 а2 an указать те из них у которых остаток от деления на M равен L(0<L<M-1)
C++ Проверить, является ли остаток от деления первой цифры числа на последнюю четным

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru