Cod sursa(job #1743201)
Utilizator | Petru G petroo | Data | 17 august 2016 19:05:16 |
---|---|---|---|
Problema | Ridicare la putere in timp logaritmic | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include <stdio.h>
long long modulo = 1999999973;
unsigned long long solve(long long x,long long n)
{
if (n == 0)
return 1;
else if (n == 1)
return x % modulo;
if (n % 2 == 0) return solve((x * x) % modulo, n/2);
if (n % 2 != 0) return (x % modulo) * solve((x * x) % modulo,(n-1)/2);
}
int main()
{
unsigned long long x, n;
freopen("lgput.in","r",stdin);
freopen("lgput.out","w",stdout);
scanf("%d %d", &x, &n);
printf("%lld",solve(x,n) % modulo);
return 0;
}