Cod sursa(job #414904)
Utilizator | laurentiu pavel laurentt | Data | 10 martie 2010 18:26:15 |
---|---|---|---|
Problema | Ridicare la putere in timp logaritmic | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.51 kb |
#include<stdio.h>
long long n,p;
void cit()
{
scanf("%lld %lld",&n,&p);
}
long long lgput(int n, int p)
{
if (p == 0)
return 1;
if(p==1)
return n;
if(p==2)
return n*n;
if(p==3)
return n*n*n;
if(p%2==0)
return (lgput(n,p/2)*lgput(n,p/2)%1999999973);
else
return (n*lgput(n,(p-1)/2)*lgput(n,(p-1)/2)%1999999973);
}
int main()
{
freopen("lgput.in","r",stdin);
freopen("lgput.out","w",stdout);
cit();
printf("%lld",lgput(n,p)%1999999973);
return 0;
}