Cod sursa(job #1393172)
Utilizator | Gavrila Alexandru sandugavrila | Data | 19 martie 2015 10:03:08 |
---|---|---|---|
Problema | Ridicare la putere in timp logaritmic | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.51 kb |
#include <cstdio>
using namespace std;
const int m = 1999999973;
long long lgexp(long long x,long long n)
{
if(n==0) return 1;
else if(n==1) return x%m;
else if(n%2==0)
return lgexp(x,n/2)%m*lgexp(x,n/2)%m;
else if(n%2!=0)
return lgexp(x,n/2)%m*lgexp(x,n/2)%m*x%m;
}
int main()
{
long long x, n;
freopen("lgput.in","r",stdin);
freopen("lgput.out","w",stdout);
scanf("%lld%lld",&x,&n);
printf("%lld",lgexp(x,n)%m);
return 0;
}