Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Modulo z ciągu fibonacciego

Ostatnio zmodyfikowano 2018-10-27 10:26
Autor Wiadomość
Trutrum
Temat założony przez niniejszego użytkownika
Modulo z ciągu fibonacciego
» 2018-10-27 00:55:07
Witam. Mam problem z tym zadaniem - W pierwszej linii wejścia podana jest liczba testów T (1 ≤ T ≤ 100). W następnych T wierszach podane są pary n, m (1 ≤ n,m ≤ 109).
Problem polega na tym że przekracza limit czasowy.

#include <cstdio>
#include <iostream>
using namespace std;
int main() {
    int t, n, m;
    scanf( "%d", & t );
    while(t--) {
        scanf( "%d %d", & n, & m );
        int an_1 = 1, an_2 = 1, an = 1;
        for( int i = 3; i <= n; i++) {
            an =( an_2 + an_1 ) % m;
            an_2 = an_1;
            an_1 = an;
       
        }
 
        printf( "%d\n", an );
    }
    return 0;
}


Czy mozna jakoś przyspieszyć algorytm? Dzięki
P-172689
pekfos
» 2018-10-27 10:26:04
To nie powinna być niespodzianka, że naiwny algorytm przekracza limit czasowy. To co masz, to najwolniejszy możliwy algorytm dla tak postawionego problemu. Skorzystaj z własności matematycznych modulo i jakichś technik optymalizacyjnych, zamiast tłumaczyć treść zadania na C++.
P-172690
« 1 »
  Strona 1 z 1