048 ABCacm

[•Teodor94]

Aici puteti discuta despre problema ABCacm.

[•Dddarius95]

Salut! Poate sa imi spuna cineva care este complexitatea oficiala? Am incercat exponentiere pe matrice cu O ( T * D^3 *logN , D=3 ) si da TLE. Sau sa verific daca sirul e periodic... dar obtin MLE.. pentru A=2013, B=2014,C=2014 mi-a dat pe laptopul meu perioada 49 074 325 in 2 secunde (MLE + TLE)...

[•klamathix]

Da, am stat È™i eu È™i m-am uitat vreo 10 minute bune care-i faza. ÃŽÈ›i ciclează când N = 1, fiindcă tu ridici la puterea N - 2  .

[•Dddarius95]

      Sorry.. nu am fost atent  .. si toate testele pe care le datusem erau cu N>=3.
      Da. Am considerat ca inmultesc ( a_i-2 a_i-1 1) * ( (0 A 0) , (1 B 0) , (0,C,1) ) = ( a_i-1 a_i 1)
si obtin M_n=M_2 *( Z^N-2), cum am notat eu M_i = ( a_i-1 a_i 1) , cel mai mic e M_2.  
      Multumesc pentru observatie!
      LE: si pentru N=2