Cod sursa(job #156605)
Utilizator | Oltean Dorin Dorin | Data | 12 martie 2008 17:32:23 |
---|---|---|---|
Problema | Ridicare la putere in timp logaritmic | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
# include <stdio.h>
using namespace std;
# define input "lgput.in"
# define output "lgput.out"
# define modulo 1999999973
# define max 100001
long long n,p,res;
void executa()
{
while(p)
{
if(p%2)
{
res+=n;
res%=modulo;
}
p/=2;
n*=n;
n%=modulo;
}
}
int main()
{
freopen(input, "r", stdin);
freopen(output, "w", stdout);
scanf("%lld%lld",&n,&p);
n%=modulo;
if(p == 0)
{
printf("1");
return 0;
}
executa();
printf("%lld",res);
return 0;
}