[TEMA]Ridicare la putere in timp logaritmic

Craciun fericit tuturor!

Rog putin ajutor din partea voastra, pentru ca ma chinui de cateva ore si nu imi dau seama unde gresesc.

Enunt -> http://www.infoarena.ro/problema/gcd

Sursa mea:

#include <fstream>

using namespace std;

ifstream fin("gcd.in");
ofstream fout("gcd.out");

int T, a, p1, p2, mod;

unsigned long long sol;

unsigned long long Ridicare(int n, int p, int m);
int Cmmdc( int a, int ;

int main()
{
fin >> T;
for ( int j = 0; j < T; ++j )
{
fin >> p1 >> p2 >> mod;
fout << (Ridicare(2, Cmmdc(p1,p2), mod) - 1) % mod << '\n';
}
fin.close();
fout.close();
return 0;
}


unsigned long long Ridicare(int n, int p, int m)
{
sol = 1;
a = n;
for (unsigned int i = 0; (1<<i) <= p; ++i ) // Luam toti bitii lui p la rand
{
	 if ( ((1<<i) & p) > 0) // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
		 sol= (sol * a) % m;
		 a=(a * a) % m; // Inmultim a cu a ca sa obtinem n^(2^(i+1))
}
return sol;
}


int Cmmdc(int a, int 
{
if ( !a ) return b;
return Cmmdc(b % a, a);
}

Pentru exemplu, raspunsul afisat este corect.
Insa, cand trimit sursa, obtin 0p.
De ce? Unde este greseala?

L.E: fout << (Ridicare(2, Cmmdc(p1,p2), mod) - 1) % mod << '\n';
aici m-am bazat pe -> http://math.stackexc...am-1-a-gcdn-m-1

Edited by Redount2k9, 25 December 2014 - 19:32.

Pai si la teste ce zice? Raspuns gresit sau ca-i prea lent?

Raspuns gresit, cum sa fie prea lent? Nu cred ca exista solutie mai rapida.

Edited by Redount2k9, 26 December 2014 - 11:49.

Pune niste cout-uri sa vezi daca iti calculeaza bine puterea. La if-ul ala din Ridicare() trebuia sau nu {} ? Ca dupa cum e indentat ar trebui {}...Daca iti calculeaza bine puterea uita-te si la cmmdc. Dar ia alte numere nu alea din exemplu, eventual mai mari.