infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Vlad Eugen Dornescu din Aprilie 01, 2010, 18:36:59

Titlul: Ridicare la putere in O(lgN)
Scris de: Vlad Eugen Dornescu din Aprilie 01, 2010, 18:36:59

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

Titlul: RÄƒspuns: Ridicare la putere in O(lgN)
Scris de: alexandru din Aprilie 01, 2010, 18:44:09

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

Titlul: RÄƒspuns: Ridicare la putere in O(lgN)
Scris de: Vlad Eugen Dornescu din Aprilie 01, 2010, 18:52:48

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

Titlul: RÄƒspuns: Ridicare la putere in O(lgN)
Scris de: alexandru din Aprilie 01, 2010, 19:26:35

Si cine te opreste sa faci asta

Cod:

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

Titlul: RÄƒspuns: Ridicare la putere in O(lgN)
Scris de: Vlad Eugen Dornescu din Aprilie 01, 2010, 19:30:31

Am facut altfel si mi-a mers \:D/