Ridicare la putere in O(lgN)

[•dornescuvlad]

Cod:

int lgput(long long int N, long long int P)
{	
	if(P==0)
		return 1;
	if(P==1)
		return N%modulo;
	if(P==2)
		return (N*N)%modulo;
	else
	{
		if(P%2==0)
			return (lgput(N,P/2))%modulo;
		else
			return (lgput(N,P/2)*N)%modulo;
	}
}

Ce ar putea fi gresit la functia asta de ridicare la putere in O(lgN) ?
Multumesc

[•alexandru92]

( lgput( N, P/2 )*lgput( N, P/2 ) )%Modulo;
Gandestete putin la relatia de recurenta http://en.wikipedia.org/wiki/Exponentiation_by_squaring

[•dornescuvlad]

Daca as face chestia aia mi-ar calcula de doua ori

Cod:

#include<iostream>
#include<fstream>
#define modulo 1999999973

using namespace std;

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

long long lgput(long long int N, long long int P)
{	
	if(P==0)
		return 1;
	else
		if(P%2==1)
			return (N*lgput(N,(P-1)/2)*lgput(N,(P-1)/2))%modulo;
		else
			return (lgput(N,P/2)*lgput(N,P/2))%modulo;
			
}
	

dureaza foarte mult si mai e si incorecta pe deasupra

[•alexandru92]

Si cine te opreste sa faci asta

Cod:

long long int a=lgput( N, P/2 );
return (a*a)%Modulo

?

[•dornescuvlad]

Am facut altfel si mi-a mers