Ridicarea la putere in timp logaritmic

Probabil au fost cateva persoane ce nu au inteles la un moment dat rezolvarea problemei Ucif in O(1) explicata de Alex si Andrei Misarca si au dorit sa inteleaga ce a facut Cosmina in prezentarea problemei.Astfel noi vom incerca sa ne jucam cu problema de mai sus dar folosind o metoda de rezolvare nu tocmai optima in cazul problemei respective , ci doar o vom folosi pentru a avea un exemplu pe care sa ne bazam.

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

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.

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 , puteti alege rezolvarea Cosminei de la problema Ucif , cu cateva modificari sa o facem in stilul celor de mai sus(cea de mai jos) :

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;   
}  

Puteti citi mai multe detalii de fundamentul matematic al acestui algoritm pe wikipedia.