Cod sursa(job #148394)

Utilizator oumbraPaul Filimoon oumbra Data 4 martie 2008 11:34:36
Problema Ridicare la putere in timp logaritmic Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <cstdio>

#define MAGIC 1999999973

long long n, p;

long long  ntothe(long long a, long long b)
{
	long t1;

	switch(b)
	{
		case 1:
			return a;
		case 0:
			return 1;
	}
	
	if(b % 2)
	{
		t1 = ntothe(a, b/2);
		return ((((t1%MAGIC)*(t1%MAGIC))%MAGIC)*(a%MAGIC))%MAGIC;
	}
	else
	{
		t1 = ntothe(a, b/2);
		return ((t1%MAGIC)*(t1%MAGIC))%MAGIC;
	}
}

int main()
{
	freopen("lgput.in", "r", stdin);
	freopen("lgput.out", "w", stdout);

	scanf("%lld%lld", &n, &p);
	
	printf("%lld\n", ntothe(n, p));

	return 0;
}