Modulo z ciągu fibonacciego
Ostatnio zmodyfikowano 2018-10-27 10:26
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 |
|
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++. |
|
« 1 » |