Ridicarea la putere in timp logaritmic

Ne vom axa doar pe determinarea ultimei cifrei a lui x^x.Metoda clasica de rezolvare presupune ridicarea la putere in timp liniar.:

?

1 2 3 4 5 6 7 8 9 10 11 12

int ucif(int x,int n,int modul) {     if(n==0) return 1;     int cif = 1;     while(n--)     {         cif = (cif*x)%modul;     }     return cif; } // Modalitate de apelare: printf("%d",ucif(9,9,10));

Din fericire,aceasta solutie va obtine punctajul maxim daca nu ma insel pe testele la problema respectiva,insa cu marirea lui n se va simti o diferenta enorma in timpul de executie, datorita complexitatii acestuia(n^2).
Pentru asta va trebui sa ne folosim de ridicarea in timp logaritmic, o rezolvare ce va imbunatati mult timpul de executie al algoritmului.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

int ucif(int x,int n,int modul) {     int cif = 1;     int a;     if(n==0) return 1;           a = x;     for (int i = 0; (1<<i ) < = n; i++)  // Luam toti biti lui p la rand     {         if ( ((1<<i) & n) > 0) // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie             cif= (cif * a) % modul;                   a=(a * a) % modul; // Inmultim a cu a ca sa obtinem n^(2^(i+1))    }     return cif; } // Modalitate de apelare: printf("%d",ucif(9,9,10));

In cazul in care doriti o rezolvare recursiva ,

?

1 2 3 4 5 6 7 8

int ucif(int x, int n,int modul)   {       int tip;     if(n==0) return 1;       if(n%2==1) return (x*ucif(x,n-1,modul))%modul;       tip=ucif(x,n/2,modul)%modul;       return tip*tip%modul;   }