Solution of Big Integers

Problema a fost una interesanta admintand 3 solutii 2 greu de implementat si una inteligenta si scurta.

Matrici

Recurenta X[i] = 2 (102), i == 1 sau (X[i-1] * 2k+1 + 2k) % 666013 se poate transpune in inmultiri de matrici

| 2k+1 1  0 |   | Xk |   | Xk+1|
| 0    1  0 | x | 2k | = | 2k  |
| 0    0  1 |   | 1  |   | 1   |

Matematica

Se observa ca elementull X[i] este suma termenilor unei progresii geometrice cu ratia 2k+1 , se aplica formula pentru suma de termeni de progresie geometrica. Sum = b*(qn-1)/(q-1). Deoarece raspunsul trebuie afisat modulo 666013 vom folosi invers modular pentru impartire.

Solutia Smen

Se identifica ciclurile si se preproceseaza Din cauza ca de la X[i] mergem la X[i] * 2k+1 + 2k se formeaza cicluri pe baza resturilor

De exemplu pentru k = 1 se formeaza ciclu la i = 333006 de la valoarea 0, pentru k = 3 la i = 166503, pentru k = 13 tot la i = 333006 cu valoarea 0.

Acum ca sa calculam restul celui de al i-lea nr din X trebuie doar sa calculam restul lui i la perioada si sa afisam restul pentru acel numar.